Juzi Zhao
email: juzi.zhao@sjsu.edu

Suresh Subramaniam
email: suresh@gwu.edu

Embedding Virtual Networks in Flexible Optical Networks with Sliceable Transponders

Keywords: Virtual networks, flexible optical networks, inter-datacenter networks, embedding, frequency slots, list scheduling

Emerging inter-datacenter applications involving data transferred, processed, and analyzed at multiple data centers, such as virtual machine migrations, real-time data backup, remote desktop, and virtual data centers, can be modeled as virtual network requests that share computing and spectrum resources of a common substrate physical interdatacenter network. Recent advances make flexible optical networks an ideal candidate for meeting the dynamic and heterogeneous connection demands between datacenters. In this paper, we address the static (offline) version of the virtual network embedding problem in flexible optical networks equipped with sliceable bandwidth variable transponders (SBVTs). The objective is to minimize the total number of required SB-VTs in the network. An Integer Linear Programming (ILP) formulation is presented, lower bounds are derived, and four heuristics are proposed and compared. Simulation results are presented to show the effectiveness of the proposed approaches.

Introduction

Flexible (or elastic) optical networks (FONs), with a fine-grained spectral spacing and variable channel center frequencies are promising for connecting geodistributed datacenters due to their capability to transfer large amounts of data as well as efficiency and flexibility of utilizing spectrum resources [START_REF] Tomkos | A tutorial on the flexible optical networking paradigm: State of the art, trends, and research challenges[END_REF][START_REF] Jinno | Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network[END_REF].

Network virtualization breaks the network's rigidly fixed pattern by enabling different virtual networks with various requirements to share the same substrate physical network. Each virtual network (VN) request is a logical topology including a set of virtual nodes interconnected by virtual links. These requests require not only communication resources on the optical links but also compute and storage resources at the physical nodes in the network. Emerging inter-datacenter applications, such as virtual machine migration, database replication/backup, and virtual data centers, can be modeled as VN requests. The problem of allocating route(s) as well as appropriate spectrum, computing, and storage re-

Model and Problem Statement

The physical inter-datacenter network topology is G p (V p , E p ), where V p is the set of nodes (each is a data center associated with an optical switch), and E p is the set of links. Each physical node has H virtual machines (VMs). Each SBVT at one physical node has C carriers. There are two fibers on each physical link with opposite directions, each has S frequency slots. The bandwidth of each frequency slot is 12.5 GHz. A number of frequency slots are allocated to each lightpath according to its spectrum requirement. The frequency slots allocated to each lightpath have to be contiguous (spectrum contiguity constraint), and the same band of frequency slots has to be allocated on each link traversed by the lightpath (spectrum continuity constraint). A guardband of G consecutive frequency slots has to be assigned between adjacent frequency slot bands allocated to different lightpaths if they share common physical links, in order to avoid interference [START_REF] Christodoulopoulos | Elastic bandwidth allocation in flexible OFDM-based optical networks[END_REF]. K shortest distance paths between each pair of nodes are precomputed. One of M possible modulation formats is assigned to each lightpath. Each modulation format m has a maximum transmission reach R m associated with it. A lightpath assigned modulation format m must has path distance less than R m . Depending on the path length, each precomputed path has a highest modulation level that can be used. The physical network is considered as transparent, therefore, no spectrum converters exist in the network.

A VN request i can be represented as a graph G i l (V i l , E i l ), where V i l is the set of virtual nodes, and E i l is the set of virtual links. For clarity, we drop subscript l which indicates a virtual or logical topology. There is a bit rate requirement Λ i k for each virtual link k i ∈ E i for bidirectional communication between the two end virtual nodes. Each virtual node j i can be mapped to one physical node of a candidate physical node set (N i j ), and requires h i j VMs. According to the candidate physical node sets of two end virtual nodes, virtual link k i has a candidate path set P i k . Path p ∈ P i k has a frequency slot requirement b i k (p), based on the path's highest modulation format m p and Λ i k , i.e., b i k (p) = Λ i k /(s p * 12.5) , where s p is spectrum efficiency of m p in Gbps/GHz. In this paper, we assume two virtual nodes of the same VN request can be mapped to one physical node as long as the VM resources permit. In this case, there are no frequency slots nor SBVTs allocated to the virtual link connecting these two virtual nodes. (We note that the proposed approaches can be easily modified if this assumption does not hold, by adding an additional constraint that no two virtual nodes of the same request can be mapped to a single physical node.)

In this paper, we adopt the multi-laser sliceable bandwidth variable transponder (SBVT) model [START_REF] Dallaglio | Routing, spectrum, and transponder assignment in elastic optical networks[END_REF]. Each SBVT has C carriers. There is a dedicated tunable laser associated with each carrier, and the bandwidth of each carrier is U GHz. A single lightpath can be assigned 1 to C carriers based on its bandwidth requirement. If more than one carriers are assigned to a single lightpath, a 2 GHz guardband will be allocated between two carriers due to the center-frequency instability issue with lasers. Note that if multiple lightpaths are assigned the same SBVT at a particular node, then the bandwidths allocated to these lightpaths cannot have any overlap. This leads to the idea of extra links in the physical network as shown in Fig. 1 frequency slot on each link can be assigned to at most one lightpath (spectrum clash constraint). This constraint applies to both physical links and extra links.

In this paper, we consider static VNE problem where a set of requests are given a priori. Each virtual node in a request is mapped to a single physical node, with sufficient available VMs, selected from its candidate physical node set. Each virtual link is mapped to a physical path p, and a band of contiguous frequency slots is allocated to the virtual link based on its bit rate requirement. Two SBVTs on source and destination nodes, respectively, of path p have to be assigned to launch and terminate lightpath; and a corresponding number of carriers on the two assigned SBVTs are allocated to the virtual link. The objective is to minimize the total number of required SBVTs to map all requests.

Algorithms

In the following, we use pnode, vnode, plink, vlink, ppath, elink, and fslot to stand for physical node, virtual node, physical link, virtual link, physical path, extra physical link, and frequency slot, respectively. In addition, we use the letter i for virtual request index, j for vnode index, k for vlink index, n for pnode index, p for ppath index, and e for elink index.

ILP Formulation

u ikq u ikq = 1 if k in i uses SBVT q on its source pnode v ikq v ikq = 1 if k in i uses SBVT q on its destination pnode τ iks τ iks = 1 if the starting fslot for vlink k in i is fslot s g iks g iks = 1 if vlink k in request i uses fslot s z ike z ike = 1 if vlink k in request i uses elink e φ ikls φ ikls = 1 if vlink k in request i uses fslot s on plink l γ ikes γ ikes = 1 if vlink k in request i uses fslot s on elink e θ iknq the number of carriers required by k in i at SBVT q of n me me = 1 if elink e is

used by some request

There are several input parameters used in the ILP: a ijn (binary), a ijn = 1 if pnode n is in the candidate set (N i j ) of pnodes to map to for vnode j in request i. h i j (integer), the number of VMs required by j in i. H n (integer), the number of VMs on n. S(p) (integer), source pnode of ppath p. D(p) (integer), destination pnode of p. S(k i ) (integer), source vnode of vlink k in request i. D(k i ) (integer), destination vnode of k in i. b i k (p) (integer), the number of fslots (including guardband) required by k in i if it is mapped to ppath p. T (e) (integer), the SBVT with elink e. B(e) (integer), the pnode with e. c i k (p) (integer), the number of carriers required by k in i if it is mapped to p. η pl (binary), η pl = 1 if p transverses plink l. The variables in ILP formulation are shown in Table 1.

From Fig. 1, it can be seen that each elink is a SBVT, so minimizing total number of required SBVTs is minimizing the total number of used elinks.

Objective: Minimize e m e Constraints: [START_REF] Tomkos | A tutorial on the flexible optical networking paradigm: State of the art, trends, and research challenges[END_REF]

n x ijn = 1 for all i, j; (2) n a ijn x ijn = 1 for all i, j (3) ij h i j x ijn ≤ H n for all n; (4) p y ikp S(p) = nx iS(k i )n for all i, k (5) p y ikp D(p) = nx iD(k i )n for all i, k; (6) p y ikp = 1 for all i, k (7) τ iks0 = g iks0 for all i, k; (8) τ iks ≥ g iks -g iks-1 for all i, k, s (9) s g iks = p b i k (p)y ikp for all i, k ; (10) s τ iks ≤ 1 for all i, k (11) s g iks ≤ S s τ iks for all i, k; (12) ik θ iknq ≤ C for all n, q (13) q u ikq = s τ iks for all i, k; (14) q v ikq = s τ iks for all i, k (15) z ike ≥ x iS(k i )B(e) + u ikT (e) -1 for all i, k, e (16) z ike ≥ x iD(k i )B(e) + v ikT (e) -1 for all i, k, e; (17) m e ≥ z ike for all i, k, e; (18) φ ikls ≥ p y ikp η pl + g iks -1 for all i, k, l, s (19) γ ikes ≥ z ike + g iks -1 for all i, k, e, s (20) ik φ ikls ≤ 1 for all l, s; (21) ik γ ikes ≤ 1 for all e, s (22) θ iknq ≥ p c i k (p)y ikp + C(x iS(k i )n -1) + C(u ikq -1) for all i, k, n, q (23) θ iknq ≥ p c i k (p)y ikp + C(x iD(k i )n -1) + C(v ikq -1
) for all i, k, n, q Constraints (1) and (2) ensure that each vnode is mapped to one of its candidate pnodes. Constraint (3) ensures that each pnode's VM capacity is not exceeded. Constraints (4) and ( 5) ensure that two end pnodes (S(p) and D(p)) of ppath p assigned to vlink k must match the two pnodes assigned to two end vnodes (S(k i ) and D(k i )) of k. Constraint [START_REF] Gong | Virtual optical network embedding (VONE) over elastic optical networks[END_REF] ensures that each vlink is mapped to a ppath. Constraints [START_REF] Wang | Network virtualization in spectrum sliced elastic optical path networks[END_REF] and ( 8) ensure spectrum contiguity constraint, where s 0 is the first fslot index. Constraint [START_REF] Yu | Novel elastic optical network embedding using reoptimized VCAT framework accompanied by hitless PPSM function[END_REF] ensures that the bit rate required by each vlink is satisfied. Note that if source pnode and destination pnode of p are the same pnode, then b i k (p) = 0, which makes s g iks = 0 since no fslot is allocated. Constraints [START_REF] Soto | Optimal occupancy mapping of virtual networks over elastic optical infrastructures[END_REF] and [START_REF] Xie | Survivable virtual optical network mapping in flexible-grid optical networks[END_REF] ensure that each vlink has one starting fslot if its two end vnodes are not mapped to the same pnode ( s g iks > 0), where S is the number of fslots on each plink. Constraint [START_REF] Chen | Cost-effective survivable virtual optical network mapping in flexible bandwidth optical networks[END_REF] ensures that each SBVT's carrier capacity is not exceeded. Constraints ( 13) and ( 14) ensure that each vlink uses at most one SBVT each at source and destination pnodes. Note that a vlink does not need SBVTs if its two end vnodes are mapped to the same pnode. Constraints [START_REF] Martinez | GMPLS/PCE-controlled multiflow optical transponders in elastic optical networks[END_REF] and [START_REF] Zhang | Dynamic traffic grooming in sliceable bandwidth-variable transponder-enabled elastic optical networks[END_REF] ensure that if a vlink uses the corresponding pnode and SBVT with elink e, then the vlink uses e. Constraint [START_REF] Christodoulopoulos | Elastic bandwidth allocation in flexible OFDM-based optical networks[END_REF] ensures that m e = 1 if at least one vlink uses elink e. Constraint (18) ensures φ ikls = 1 if k uses plink l and fslot s. Constraint (19) ensures γ ikes = 1 if k uses elink e and fslot s. Constraints (20) and ( 21) ensure that each fslot on each (extra) physical link can be assigned to at most one vlink. Constraints ( 22) and ( 23) ensure that the number of carriers of SBVT q on pnode n allocated to k (i.e., θ iknq ) depends on the number of required carriers (i.e., p c i k (p)y ikp ). If source vnode and destination vnode of k are not mapped to n (i.e., x iS(k i )n = 0 and x iD(k i )n = 0) or SBVT q is not assigned to k (i.e., u ikq = 0 and v ikq = 0), then θ iknq can be set to 0. If there is a constraint that no two virtual vnodes of the same request can be mapped to a single pnode, then we need another constraint (24) j x ijn ≤ 1 for all i, n.

Lower Bounds

LB1 This bound is based on (1) each vlink's lightpath requires 0 or more carriers of SBVTs at the source and destination pnodes to which the end vnodes are mapped, (2) each SBVT has C carriers, and (3) there are S fslots on each plink.

For each vlink k of request i, according to the distance of each candidate ppath p i k in set P i k (in turn, the modulation format) and the bit rate requirement Λ i k , we can calculate the number of required fslots as b i k (p) (including guardband) and the number of carriers c i k (p) that need to be allocated to k of i if it is mapped to ppath p. (b i k (p) and c i k (p) are 0 if p is a dummy ppath with same end pnodes.) For vlink k of i, we can find the minimum number of carriers that have to be allocated as ĉik = min p c i k (p). b i k (q) fslots will be allocated on every plink l along the ppath q ik that achieves ĉik .

For each plink l, there are several ppaths using fslots on it (according to the above minimum carrier allocation). Each ppath q ik using l requires the minimum fslot b i k (q). For each ppath q ik , among all candidate ppaths for k, find the minimum number of required carriers g ikl if plink l is not used by k. Let v q = g ikl -ĉ ik (i.e., if k does not use plink l, v q more carriers have to be allocated). We now formulate a 0/1 knapsack problem (which can be solved easily) to obtain LB1. Let the capacity of knapsack be S + G (G is guardband); there are several items with weight b i k (q) and value v q . The objective of 0/1 knapsack is to maximize total value of knapsack with weight constraint. Suppose the result is Z l ; this means that y l = q v q -Z l more carriers are required to satisfy all requests. Let Y = ik ĉik + l y l . Then LB1 = Y /C . The time complexity to compute LB1 is O(IKV 2 M + LIK(S + G)), where I is number of requests, K is maximum number of vlinks per request, V is number of candidate pnodes per vnode, M is number of ppaths for each pair of pnodes, and L is number of plinks. LB2 LB2 is obtained by observing that (1) vlinks that share an end vnode must be allocated carriers at a single pnode (the pnode to which the end vnode is mapped) and (2) capacity constraint of each pnode (H VMs).

Consider a vnode j which has several candidate pnodes n 1 , n 2 , n 3 , .... There are several vlinks k 1 , k 2 , k 3 , ... that share j as one end vnode. If j is mapped to n 1 , then some carriers of SBVTs at pnode n 1 will be allocated to k 1 , k 2 , k 3 , .... We can find the minimum number of required carriers for these vlinks if j is mapped to n 1 based on the candidate ppaths of k 1 , k 2 , k 3 , .... Denote Q j (n 1 ) as the value. Similarly, Q j (n 2 ), Q j (n 3 ), ... can be calculated. Therefore, we can find the best pnode mapping for vnode j in terms of the number of required carriers cj = min(Q j (n 1 ), Q j (n 2 ), Q j (n 3 ), ...).

For each pnode n, there are several vnodes j using VMs on it (according to the above allocation). Each vnode has a VM requirement h j . For all vlinks with end vnode j, find the minimum number of required carriers g jn for these vlinks if j is not mapped to n. Let v j = g jncj (i.e., if j is not mapped to n, v j more carriers have to be allocated). We again have a 0/1 knapsack problem for n. The capacity of the knapsack is H (the VM capacity), there are several items, with item j having weight h j and value v j . The objective is to maximize total value of knapsack with weight constraint. Suppose the result is Z n , which means y n = j v j -Z n more carriers are required to satisfy all requests. Let Y = j cj + n y n . Then LB2 = Y /C . The time complexity to compute LB2 is O(IKV 2 M + NIJH), where N is the number of pnodes, J is the maximum number of vnodes per request, and H is the number of VMs per pnode.

Proposed Heuristics

Although ILP can provide an optimal solution, it only works for small instances due to high time complexity. For larger instances, we propose two heuristics based on list scheduling, and then propose two improved meta-heuristics based on Tabu Search. Note that since VNE problem is NP-hard, the heuristics may occasionally fail to produce a result even though a valid mapping exists.

LL Heuristic

This heuristic first assigns a weight W i to each request i based on its requirement, then requests are sorted by decreasing order of weights and mapped one by one (Steps 1 and 4 in Algorithm 1). Regarding a particular i under consideration, a weight ω ik is assigned to each vlink k i , and the vlinks are sorted by decreasing order of weights and are mapped following this order (Steps 4.a and 4.b). For vlink k i being mapped, every possible candidate (as a combination of a ppath, a band of contiguous fslots and two SBVTs at source and destination pnodes respectively) is assigned a weight, and the combination with minimum weight is allocated to k i (Steps 4.b(1)-4.b(3)).

Weight W i is calculated as W i = max ĥi hμ , Λi Λν , where ĥi = j h i j is the total number of VMs required by i, Λi = k Λ i k , is the total bit rate requirement of i, h = i ĥi , Λ = i Λi , μ = ij f i j where f i j is the number of pnodes the vnode j can be mapped to, and ν = ik r i k where r i k is the number of candidate ppaths the vlink k can be mapped to. Decreasing order of request weights gives higher priority to resource-intensive requests.

Before mapping the requests, we check (in Step 2 CheckTrivialRequests) whether any request i can be mapped to a pnode n without affecting vnode mapping of other requests (i.e., all other vnodes can still be mapped to n if n is one of their candidate pnodes). It is best to map an entire request to a single pnode if possible since this mapping won't use any fslots nor SBVTs. There is another check made before mapping VN requests and after every vlink mapping 3)). There is a VM limit at every pnode and a fslot limit on each plink; the purpose of CheckOneCandidate is to share these limited resources fairly by first mapping vnodes and vlinks of all requests that have only one pnode and ppath to map to.

For a particular request i under consideration, each of its unmapped vlinks k is assigned a weight ω ik (Step 4.a) as bi k /m k i , where m k i is the number of possible candidate ppaths for k, and bi k is the current minimum number of required fslots for k among the m k i candidate ppaths. The vlinks of i are sorted in decreasing order of weights to first map vlinks requiring more fslots and having fewer candidate ppaths. Now we describe the vlink mapping steps (Steps 4.b(1)-4.b(3)). For each unmapped vlink k (with source vnode s(k) and destination vnode d(k)) mapping, all of its currently available candidate x, as a combination of ppath p (with source pnode s(p) and destination pnode d(p)), a band of fslots f on p, SBVT t s (p) at s(p), and SBVT t d (p) at d(p), will be assigned a weight

Δ x = h x +t x +b k (p)/S+c k (p)/C, where h x = max(m s(k) h s(k) /H s(p) , m d(k) h d(k) /H d(p) ) if s(p) = d(p), otherwise h x = (m s(k) h s(k) + m d(k) h d(k) )/H s(p) , where m s(k) = 0 (m d(k) = 0) if s(k) (d(k)
) has already been mapped, otherwise they are set as 1; andH s(p) (H d(p) ) is the number of currently available VMs at s(p) (d(p)); t x is the number of newly allocated SBVTs (which have not been allocated so far) to k; b k (p) and c k (p) are the numbers of required fslots and required carriers, respectively, if k is mapped to p; S is the fslots capacity of each plink; and C is the number of carriers per SBVT. Vlink k is mapped to the candidate achieving the minimum value Δ = min x Δ x . After that, VM, SBVTs (with carriers), and fslot resources are updated for the corresponding plinks and pnodes (allocated to vlink k and its end vnodes). At last, CheckOneCandidate function is called since the mapping of k might result in changes of other vnodes'/vlinks' available mapping candidates. This procedure is repeated until all vlinks of i are mapped. The time complexity of LL is O(

h s(k) (h d(k) ) is the number of required VMs for s(k) (d(k)),
I 3 J 2 NK + V 2 MSI 3 K 3 ).
Note that if no two vnodes of the same request can be mapped to a single pnode, then there is no TrivialRequestCheck() function. Dummy paths (with the same end pnodes) will not be considered as candidate ppaths in all steps.

ALL Heuristic ALL heuristic is similar to LL heuristic with the difference that LL first sorts VN requests, then does the vlink mapping for these requests one by one. In ALL heuristic, all vlinks of all requests are sorted by decreasing order of their weights ω ik (defined in LL heuristic), and the vlinks are then mapped one by one. The time complexity of ALL is the same as LL.

Tabu Search We utilize Tabu Search meta-heuristic to improve the LL and ALL heuristics performance, called LL-TS and ALL-TS, respectively. The main idea of Tabu search is to utilize a neighborhood search procedure to iteratively generate a better solution from one potential solution by exploring the neighborhood of current potential solution, until an attempt limit. In LL-TS algorithm (ALL-TS algorithm), the Tabu search method is utilized to iteratively generate different ordered sets of VN requests (virtual links), each order is treated as a Tabu Search solution. Given this order, the remaining steps in LL (ALL) are kept the same to find the number of required SBVTs. The initial request (vlink) order is the one used in LL (ALL). To create a new ordered set based on current order, two VN requests (vlinks) in current order are randomly selected and swapped. To improve performance, Θ different new ordered sets are created for each current order (according to different swaps). The new order that results in minimum number of required SBVTs will be used as current order for the next iteration. The procedure is repeated for Φ iterations. The larger the Θ and Φ values, the better the performance, but the longer simulation time. The time complexity is O(ΘΦI 3 J 2 NK + ΘΦV 2 MSI 3 K 3 ).

Simulation Results

We present results for two network topologies, the small 6-node network, shown in Fig. 1 and Google data center network, shown in Fig. 2.

There are 3 modulation levels used in the simulations: DP-QPSK, DP-8QAM and DP-16QAM, and their corresponding transmission reach limits are 3000 km, 1000 km, and 650 km, respectively [START_REF] Martinez | GMPLS/PCE-controlled multiflow optical transponders in elastic optical networks[END_REF]. The spectrum efficiencies (in Gbps/GHz) of the three modulation formats are: 4, 6, and 8. The guardband is set as G = 1 frequency slot. The bandwidth of each carrier in SBVT is 25 GHz. There are 3 precomputed paths for each pair of physical nodes. Each virtual network request has either 3 or 4 virtual nodes (selected randomly). Each virtual node has randomly 1-3 physical node candidates. The probability that there is a virtual link between each pair of virtual nodes is set as 0.8 for small 6-node network and 0.6 for Google Network. The bit rate requirement for each virtual link is randomly set in the range 100 -500 Gbps.

Numerical Results for 6-node Network

In this section, we compare the results of ILP, lower bounds, and four heuristics for small 6-node network topology. We assume that each physical node has 30 VMs and there are 30 frequency slots on each physical link. Each virtual node requires a random number between 1 and 5 VMs. The number of carriers per SBVT is set as C = 5. Let I denote the number of VN requests. The value of Θ is set as I(I -1)/2 and the value of Φ is set as 500 for Tabu search algorithms. Sample results for 1 -14 virtual network requests are shown in Table 2 (15 requests turn out to be infeasible due to node capacity), where LB is the minimum of LB1 and LB2; and inf means a feasible result was not found.

It can be seen that ALL algorithm outperforms LL algorithm, but both produce infeasible solutions for some cases. Tabu Search can improve heuristic results, suggesting that the order of requests (or virtual links) can affect performance especially for the cases that resources requirements are close to resources capacity (i.e., 13 and 14 request cases). The LB values are not far away from optimal ILP results.

Numerical Results for Google Network

For the larger Google network topology, we show the results for lower bounds, LL, ALL, LL-TS, and ALL-TS, as the average of 10 seeds simulation results. We assume that each physical node has 1000 VMs, and there are 320 frequency slots on each link (as optical C-band is 4000 GHz and each frequency slot is 12.5

GHz). The number of required VMs for each virtual node is randomly selected in {10, 20, 30, 40, 50}. The value of Θ is set as 20 and value of Φ is set as 25. Fig. 3 shows the number of required SBVTs as a function of number of requests when there are 5 carriers per SBVT. Fig. 4 shows number of required SBVTs for 50 requests versus number of carriers per SBVT. Fig. 5 shows simulation results for mixed virtual links' bit rate requirements of 50 requests, where α percentage of virtual links have bit rate requirement in range 100 -200 Gbps, 1α percentage of virtual links have bit rate requirement in range 400-500 Gbps (when there are 5 carriers per SBVT). These results confirmed that performance of ALL is better than the performance of LL. Tabu Search produces feasible solutions when LL and ALL fail as shown in

Conclusions

A virtual network embedding problem is investigated in flexible optical interdatacenter networks equipped with sliceable transponders. The objective is to minimize the total number of required sliceable transponders. We proposed an Integer Linear Programming formulation, two lower bounds, two heuristics based on list scheduling, and two meta-heuristics based on Tabu Search. Simulation results show that the Tabu Search variant of two proposed heuristics achieve quite good performance compared to the derived lower bounds.

  (only three SBVTs at node A are shown in the figure for illustration purpose). The original network has 9 links. The links between SBVTs and physical nodes can be treated as extra links. All lightpaths assigned SBVT a at node A will transverse extra link 10. Recall that for FONs, a single

.

Fig. 1 .

 1 Fig. 1. Extra links introduced by transponders.

1 1 : 6 Step 4 7 Step 4 8 foreach unmapped vlink k of request i do 9 foreach 12 Step 4 13 Step 4

 1647489124134 Step Assign weight Wi to each VN request i; and sort the requests in decreasing order of weights 2 Step 2: TrivialRequestCheck() 3 Step 3: CheckOneCandidate() 4 Step 4: Schedule ordered unmapped requests one by one 5 foreach sorted request i do .a: Assign weight ω ik to each unmapped vlink k of i, and sort them in decreasing order of weights .b: Schedule ordered unmapped vlinks of i one by one allocation-combination x (including candidate ppath p, fslot band f on p, SBVT ts(p) at source pnode of p, SBVT t d (p) at destination pnode of p) do 10 Step 4.b(1): Calculate Δx the weight of x 11 end .b(2): Map vlink k to allocation-combination x that achieves minx Δx

.

Fig. 2 .

 2 Fig. 2. Google Data Center Network with link distance in km.

Fig 3 .

 3 The differences between Tabu Search and lower bound are on average 10%, 17%, and 11.2% in Figs3, 4, and 5 respectively.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Number of Required SBVTs vs. Number of Carriers per SBVT.

Table 1 . Notations Symbol Meaning xijn xijn = 1 if vnode j in request i is mapped to pnode n y ikp y ikp = 1 if vlink k in i is mapped to ppath p, where p could be a dummy path with source pnode and destination pnode being a same pnode

 1

Table 2 .

 2 Number

	of Required SBVTs in		200
	6-node network I ILP LB LL ALL LL-TS ALL-TS 5 6 4 6 6 6 6 6 8 6 8 8 8 8 7 9 7 11 9 9 9 8 10 8 14 12 11 10 9 10 8 18 14 12 10 10 10 8 20 14 12 12	Number of Required SBVTs	50 100 150		LL ALL LL-TS ALL-TS LB
	11 12 10 inf 19 12 14 12 inf 21	15 18	16 14		0	0	Number of Virtual Network Requests 2 0 4 0 6 0	8 0
	13 16 13 inf inf 14 18 14 inf inf	20 22	20 22	Fig. 3. Number of Required SBVTs vs. Number of Requests.

Acknowledgment

This work was supported in part by NSF grants CNS-1813617 and CNS-1813772.


Boping Jiang

Sanjay K Bose

Ke Chen

Gangxiang Shen
email: shengx@suda.edu.cn

Shuiping Jie

Availability-Guaranteed Slice Provisioning in Wireless-Optical Broadband Access Networks Supporting Mobile Edge Computing

Keywords: WOBAN, MEC, Slice Provisioning, Availability Guarantee. 1

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

5G access networks carry various applications that require ultra-fast data transfer and flexible device support. WOBAN [START_REF] Shen | Fixed mobile convergence architectures for broadband access: integration of EPON and WiMAX[END_REF] [START_REF] Chowdhury | Hybrid wireless-optical broadband access network (WONAN): prototype development and research challenges[END_REF] shows promise as potential 5G access infrastructure. To efficiently share physical resources in such a system, it would be desirable to implement network slicing [3][4] to support diverse applications [START_REF] Samdanis | From network sharing to multi-tenancy: the 5G network slice broker[END_REF], with each slice flexibly running a specific application. Although there have been studies on how to efficiently provision slices in a 5G access network [START_REF] Gong | Virtual network embedding for collaborative edge computing in optical-wireless networks[END_REF], how to guarantee the availability of each provisioned slice is still not well investigated. A guaranteed availability is critical for a service provider to meet its service level agreement (SLA) when provisioning slices to its users [START_REF] Clouqueur | Availability analysis of span restorable mesh networks[END_REF][8] [START_REF] Shao | Availability-aware routing for large-scale hybrid wireless-optical broadband access network[END_REF]. Therefore, it is vital to address this issue for slice provisioning in a WOBAN. Our earlier work in [START_REF] Chen | Maximizing availability-weighted slice capacity for sliceable wireless-optical broadband access networks[END_REF] reported on a preliminary study maximizing the availability-weighted slice capacity for a sliceable WOBAN, in which, however, the availability of each provisioned slice is not guaranteed. From the SLA point of view, it is more practical to consider slice provisioning with a guaranteed availability for each slice. Therefore, this study focuses on the problem of provisioning availability-guaranteed slices in a sliceable WOBAN. To formulate the slice availability, four failure scenarios, including the failures of a fiber link, a microwave link, a BS node, and an OLT, are considered. A new definition of availability is made for a slice that functions only partially. To maximize the number of slices provisioned with guaranteed availability, we formulate the problem into an ILP model and develop a simple but effective heuristic algorithm. Simulation results show the efficiency of the proposed approaches.

2

Sliceable WOBAN Supporting MEC Fig. 1 shows a typical WOBAN example, which contains two passive optical networks (PONs) [START_REF] Mcgarry | WDM Ethernet passive optical networks[END_REF][12] and one wireless mesh network (WMN) [START_REF] Akyildiz | A survey on wireless mesh networks[END_REF] [START_REF] Chen | Hybrid fiber and microwave restoration for enhancing availability of fiber-wireless integrated networks[END_REF]. Each PON is composed of an OLT and several ONU-BSs, each of which consists of an optical network unit (ONU) and a wireless BS. In the WMN, the ONU-BSs and BSs are connected via microwave links and each BS provides wireless access for local users. Unlike a conventional WOBAN, which merely provides communication capacity for users, here we also consider the computing/storage (C/S) capacity, measured in units of virtual machines (VMs), available at each BS node to support the MEC function [START_REF] Zhang | Energy-efficient offloading for mobile edge computing in 5G heterogeneous networks[END_REF]- [START_REF] Mao | A survey on mobile edge computing: the communication perspective[END_REF] that is critical for the 5G access network [START_REF] Rimal | Mobile edge computing empowered fiber-wireless access networks in the 5G era[END_REF]. A sliceable WOBAN is a WOBAN that can be divided into multiple slices with each provisioning services for different applications. A slice is considered as an independent network consisting of multiple virtual nodes and virtual links. Fig. 1 also shows the example of a slice, in which virtual nodes are connected via virtual links and are assigned with C/S capacities for supporting MEC. Each virtual node is embedded in a physical node and each virtual link is mapped onto a physical path traversing multiple physical links. Based on a sliceable WOBAN introduced in the previous section, our problem is to maximize the number of slices provisioned with guaranteed availability subject to limited communication and C/S capacities. For this, we first define a new availability measure for a WOBAN slice. This is followed by an ILP model and heuristic algorithms that maximize the number of slices provisioned.

Definition of Slice Availability

The availability of a system is generally defined as 𝐴 = 𝑀𝑇𝑇𝐹/(𝑀𝑇𝑇𝐹 + 𝑀𝑇𝑇𝑅), where MTTF is the mean time to failure and MTTR is the mean time to repair of the system [START_REF] Clouqueur | Availability analysis of span restorable mesh networks[END_REF]. If a system consists of multiple (n) components and the failure of any component would cause the failure of the system, then its MTTF and MTTR can be derived as 𝑀𝑇𝑇𝐹 = 1 ∑ 𝜆 . ⁄ , where 𝜆 . and 𝑀𝑇𝑇𝑅 . are the respective mean failure rate and MTTR of the 𝑖 56 system component. Note that the above equation holds when the probability of a single component failure is much higher than that of a two-component simultaneous failure. This condition is true in most cases since in general 𝑝 1 ≫ 𝑝 1 • 𝑝 9 where 𝑝 . is the failure probability of a component and is typically very small.

To calculate the availability of a WOBAN slice, we first define notations as follows.

Sets: P

The set of OLTs, each of which corresponds to a PON.

N

The set of BS nodes, which can be ONU-BSs or pure BSs.

L

The set of fiber links. Each optical distributed network (ODN) of a PON is considered as a fiber link between an OLT and multiple ONUs.

M

The set of microwave links in the WMN, each of which connects a pair of BS nodes.

S

The set of slices.

𝑽 𝒔

The set of virtual links in slice s. 𝑲 𝒗

𝒔

The set of the candidate paths in the physical topology that are eligible to establishing virtual link v of slice s.

Parameters:

𝐵 ?

@

The capacity required by virtual link v in slice s. 𝜃 ?,C @,D This takes the value of 1 if the 𝑘 56 path for establishing virtual link v in slice s passes BS node x; 0, otherwise. 𝜎 ?,C @,G This takes the value of 1 if the 𝑘 56 path for establishing virtual link v in slice s passes OLT p; 0, otherwise. α ?,C @,I This takes the value of 1 if the 𝑘 56 path for establishing virtual link v in slice s passes fiber link l; 0, otherwise. 𝜇 ?,C @,K This takes the value of 1 if the 𝑘 56 path for establishing virtual link v in slice s passes microwave link m; 0, otherwise.

𝑀𝑇𝑇𝐹 ?,C @

The MTTF of the 𝑘 56 path that can be used for establishing virtual link v in slice s. 𝑀𝑇𝑇𝑅 ?,C

@

The MTTR of the 𝑘 56 path for establishing virtual link v in slice s.

Variables:

𝛽 ?,C @ A binary variable that equals 1 if virtual link v in slice s is mapped onto (or established via) its 𝑘 56 eligible path; 0, otherwise.

𝐴 @

The estimated availability of slice s. Based on the above notations, we can calculate 𝑀𝑇𝑇𝐹 ?,C @ for each virtual link in a slice, which can be seen as a serial system consisting of multiple components, i.e., the physical links and nodes traversed by the virtual link. This is derived as

𝑀𝑇𝑇𝐹 ?,C @ = 1 ∑ M N O NPQ = 1 ∑ M Q R∈𝑳 U∑ M V W∈𝑴 U∑ M Y Z∈𝑵 U∑ M \ ]∈𝑷 ∀𝑠 ∈ 𝑺, 𝑣 ∈ 𝑽 𝒔 , 𝑘 ∈ 𝑲 𝒗 𝒔 (1)
where 𝜆 1 = α ?,C @,I • 𝜆 I • 𝑑 I , 𝜆 9 = 𝜇 ?,C @,K • 𝜆 K • 𝑑 K , 𝜆 e = θ ?,C @,D • 𝜆 D and 𝜆 g = σ ?,C @,G • 𝜆 G . Specifically, 𝑑 I and 𝑑 K are the physical distances of a fiber link and a microwave link in units of km, 𝜆 I and 𝜆 K are the failure rates (in FIT per km) of the fiber link and the microwave link, and 𝜆 D and 𝜆 G are the failure rates (in FIT) of a BS node and an OLT node. Here we assume that a pure BS and an ONU-BS have the same failure rate and require the same repair time. Similarly, we can calculate 𝑀𝑇𝑇𝑅 ?,C @ for each slice virtual link by [START_REF] Chowdhury | Hybrid wireless-optical broadband access network (WONAN): prototype development and research challenges[END_REF].

𝑀𝑇𝑇𝑅 ?,C @ = ∑ M N •ijjk N O NPQ ∑ M N O NPQ = l Q Ul V Ul Y Ul \ ∑ M Q R∈𝑳 U∑ M V W∈𝑴 U∑ M Y Z∈𝑵 U∑ M \ ]∈𝑷 ∀𝑠 ∈ 𝑺, 𝑣 ∈ 𝑽 𝒔 , 𝑘 ∈ 𝑲 𝒗 𝒔 (2)
where

𝜑 1 = ∑ (𝜆 1 • 𝑀𝑇𝑇𝑅 I ) I∈𝑳 , 𝜑 9 = ∑ (𝜆 9 • 𝑀𝑇𝑇𝑅 K ) K∈𝑴
, 𝜑 e = ∑ (𝜆 e • 𝑀𝑇𝑇𝑅 D ) D∈𝑵 , and 𝜑 g = ∑ (𝜆 g • 𝑀𝑇𝑇𝑅 G ) G∈𝑷 . 𝜆 1 , 𝜆 9 , 𝜆 e , and 𝜆 g have the same definitions as in (1), and 𝑀𝑇𝑇𝑅 I , 𝑀𝑇𝑇𝑅 K , 𝑀𝑇𝑇𝑅 D , and 𝑀𝑇𝑇𝑅 G are the MTTRs of a fiber link, a microwave link, a BS node, and an OLT, respectively. Therefore, (2) calculates the average repair time of a virtual link.

It is important to note that in a network slice consisting of multiple virtual links, a single network failure would not cause all the virtual links to fail as a partial set of virtual links may still be functioning. This implies that when calculating the availability of a slice, we should not simply consider a zero-one situation, but consider the capacities of the virtual links that still functions when a network failure is being repaired. This led us to define a new availability, specifically for a partially functioning system, given as

𝐴 @ = n OopWqR r Un ]qpsNqR r n sosqR r ∀𝑠 ∈ 𝑺 (3)
Here 𝐶 5u5vI @ is the time-weighted total capacity provisioned by a slice, 𝐶 /uwKvI @ is the time-weighted total capacity provisioned by the slice during the period that the slice does not incur a failure, and 𝐶 Gvw5.vI @ is the time-weighted total capacity provisioned by a partially functioning slice when a network failure is being repaired. The three terms are derived as follows.

𝐶 /uwKvI @ = ∑ (𝛽 ?,C @ • 𝑀𝑇𝑇𝐹 ?,C @ ) • 𝐵 ? @ ?∈𝑽 𝒔 ,C∈𝑲 𝒗 𝒔 ∀𝑠 ∈ 𝑺 (4)
𝐶 5u5vI @ = ∑ (𝛽 ?,C @ • (𝑀𝑇𝑇𝐹 ?,C @ + 𝑀𝑇𝑇𝑅 ?,C @ )) • 𝐵 ? @ ?∈𝑽 𝒔 ,C∈𝑲 𝒗 𝒔 ∀𝑠 ∈ 𝑺 [START_REF] Samdanis | From network sharing to multi-tenancy: the 5G network slice broker[END_REF] In ( 4), 𝛽 ?,C @ • 𝑀𝑇𝑇𝐹 ?,C @ is the MTTF of virtual link v if its candidate path k is used for establishing the virtual link. Thus, (4) finds the total time-weighted capacity provisioned by the slice in the period that the slice does not incur a failure. In [START_REF] Samdanis | From network sharing to multi-tenancy: the 5G network slice broker[END_REF], 𝛽 ?,C @ • (𝑀𝑇𝑇𝐹 ?,C @ + 𝑀𝑇𝑇𝑅 ?,C @ ) is the sum of the MTTF and the MTTR of virtual link v if its candidate path k is used for establishing the virtual link. Therefore, (5) finds the total time-weighted capacity provisioned by slice s.

To derive 𝐶 Gvw5.vI @ , we need to consider the different network failure scenarios, including the failures of a fiber link, a microwave link, a BS node, and an OLT. We first define the total time-weighted capacity provided by a partially functioning slice when one of the four network failure scenarios occurred and the failure is being repaired as follows.

𝐵 Gvw5.vI @,I = ∑ (𝛽 ?,C @ • 𝑀𝑇𝑇𝑅 I • 𝐵 ? @ • (1 -α ?,C @,I ))

?∈𝑽 𝒔 ,C∈𝑲 𝒗 𝒔 ∀𝑠 ∈ 𝑺, 𝑙 ∈ 𝑳 (6)

𝐵 Gvw5.vI @,D = ∑ (𝛽 ?,C @ • 𝑀𝑇𝑇𝑅 D • 𝐵 ? @ • (1 -θ ?,C @,D )) ?∈𝑽 𝒔 ,C∈𝑲 𝒗 𝒔 ∀𝑠 ∈ 𝑺, 𝑥 ∈ 𝑵 (7) 𝐵 Gvw5.vI @,G = ∑ (𝛽 ?,C @ • 𝑀𝑇𝑇𝑅 G • 𝐵 ? @ • (1 -σ ?,C @,G )) ?∈𝑽 𝒔 ,C∈𝑲 𝒗 𝒔 ∀𝑠 ∈ 𝑺, 𝑝 ∈ 𝑷 (8)
𝐵 Gvw5.vI @,K = ∑ (𝛽 ?,C @ • 𝑀𝑇𝑇𝑅 K • 𝐵 ? @ • (1 -𝜇 ?,C @,K )) ?∈𝑽 𝒔 ,C∈𝑲 𝒗 𝒔 ∀𝑠 ∈ 𝑺, 𝑚 ∈ 𝑴 (9)
Here 𝐵 Gvw5.vI @,I

is the total remaining capacity of slice s weighted by the mean time to repair the failure of fiber link l that affects the slice. 𝐵 Gvw5.vI @,D is similar to 𝐵 Gvw5.vI @,I for the failure of a BS node, 𝐵 Gvw5.vI @,G is for the failure of an OLT, and 𝐵 Gvw5.vI @,K is for the failure of a microwave link. Then, we can derive 𝐶 Gvw5.vI @ as 𝐶 Gvw5.vI

@ = ∑ M R •| R •} ]qpsNqR r,R Ĩ∈𝑳 + ∑ M W •| W •} ]qpsNqR r,W K∈𝑴 + ∑ M Z •} ]qpsNqR r,Z D∈𝑵 + ∑ M ] •} ]qpsNqR r,] G∈𝑷 ∀𝑠 ∈ 𝑺 (10)
where

𝑊 = ∑ (𝜆 I • 𝑑 I ) I∈𝑳 + ∑ (𝜆 K • 𝑑 K ) K∈𝑴 + ∑ 𝜆 D D∈𝑵 + ∑ 𝜆 G G∈𝑷
denotes the mean failure rate of a WOBAN.

Because (3) is nonlinear, we convert it to linear for subsequent ILP modeling. For this, we define a new variable 𝜀 ?,C @ to replace the nonlinear term 𝛽 ?,C @ • 𝐴 @ and convert (3) to ( 11)-( 15) as follows.

∑

(𝜀 ?,C @ • (𝑀𝑇𝑇𝐹 ?,C @ + 𝑀𝑇𝑇𝑅 ?,C @ )) • 𝐵 ?

@ ?∈𝑽 𝒔 ,C∈𝑲 𝒗 𝒔 = 𝐶 /uwKvI @ + 𝐶 Gvw5.vI @ ∀𝑠 ∈ 𝑺 (11)
𝜀 ?,C @ ≤ 𝛽 ?,C @ ∀𝑠 ∈ 𝑺, 𝑣 ∈ 𝑽 𝒔 , 𝑘 ∈ 𝑲 𝒗 𝒔

𝜀 ?,C @ ≤ 𝐴 @ ∀𝑠 ∈ 𝑺, 𝑣 ∈ 𝑽 𝒔 , 𝑘 ∈ 𝑲 𝒗 𝒔 [START_REF] Akyildiz | A survey on wireless mesh networks[END_REF] 𝜀 ?,C @ ≥ 𝐴 @ -ƒ1 -𝛽 ?,C @ " ∀𝑠 ∈ 𝑺, 𝑣 ∈ 𝑽 𝒔 , 𝑘 ∈ 𝑲 𝒗 𝒔 [START_REF] Chen | Hybrid fiber and microwave restoration for enhancing availability of fiber-wireless integrated networks[END_REF] 𝜀 ?,C @ ≥ 0 ∀𝑠 ∈ 𝑺, 𝑣 ∈ 𝑽 𝒔 , 𝑘 ∈ 𝑲 𝒗 𝒔 (15)

ILP Model

We develop an ILP model to maximize the number of slices provisioned with guaranteed availability. In addition to the terms defined earlier, the additional sets, parameters, and variables of the ILP model are defined as follows.

Sets: 𝑰 𝒔

The set of virtual nodes in slice s.

Parameters:

𝐶𝑆 .

@

The C/S capacity required by virtual node i in slice s in units of VMs (for supporting MEC).

𝐵 KvD

The maximum transmission capacity of a PON (i.e., the maximum transmission capacity of its OLT).

𝑇 K

The maximum transmission capacity of microwave link m.

𝐶 D

The total C/S capacity deployed at physical node x. 𝛾 .,D @ This takes the value of 1 if virtual node i in slice s is mapped onto physical node x, which means that this slice has local users served by the current physical node; 0, otherwise.

Variables:

𝛿 @ A binary variable that equals 1 if slice s is successfully provisioned; 0, otherwise. The objective and the constraints of the model are as follows.

Objective: maximize ∑ 𝛿 @ @∈𝑺 Subject to: ∑ 𝛽 ?,C @ • σ ?,C @,G • 𝐵 ? @ @∈𝑺,?∈𝑽 𝒔 ,C∈𝑲 𝒗 𝒔 ≤ 𝐵 KvD ∀𝑝 ∈ 𝑷

∑ 𝛽 ?,C @ • 𝜇 ?,C @,K • 𝐵 ? @ @∈𝑺,?∈𝑽 𝒔 ,C∈𝑲 𝒗 𝒔 ≤ 𝑇 K ∀𝑚 ∈ 𝑴

∑ 𝛽 ?,C @ C∈𝑲 𝒗 𝒔 = 𝛿 @ ∀𝑠 ∈ 𝑺, 𝑣 ∈ 𝑽 𝒔 (18)

∑ (𝛿 @ • ∑ 𝛾 .,D @ • 𝐶𝑆 . @ .∈𝑰 𝒔 ) @∈𝑺 ≤ 𝐶 D ∀𝑥 ∈ 𝑵 (19) 𝐴 @ ≥ 0.99999 ∀𝑠 ∈ 𝑺 (20)
The objective is to maximize the number of slices provisioned with guaranteed availability. In addition to (11)-( 15), we also have constraints ( 16)-(20). Constraint [START_REF] Abbas | Mobile edge computing: a survey[END_REF] ensures that the sum capacity of all the slice virtual links that share a common PON should not exceed the maximum transmission capacity of the PON. Constraint [START_REF] Mao | A survey on mobile edge computing: the communication perspective[END_REF] ensures that the sum capacity of all the slice virtual links that traverse a common microwave link should not exceed its maximum transmission capacity. Constraint [START_REF] Rimal | Mobile edge computing empowered fiber-wireless access networks in the 5G era[END_REF] means that a slice is fully provisioned only if all of its virtual links are established. Constraint (19) ensures that the sum C/S capacity required by all the slice nodes should not exceed the C/S capacity at each physical node. Constraint (20) ensures the availability of each slice.

Heuristic Algorithms

We have developed two heuristics for the above slice provisioning problem which are expected to be computationally easier than the optimization described earlier. Specifically, we consider two types of link metrics when searching for a path for establishing a slice virtual link. The first metric is based on the length of each physical link, referred to as Heu_length. Note that the physical length of a link essentially corresponds to the unavailability of the link since they hold a linear relationship. The second metric considers the load of each physical link in addition to its unavailability, referred to as Heu_load. The steps of these two algorithms are the same except for the metrics adopted, which include the steps of virtual node mapping and virtual link mapping.

Specifically, in the Heu_load algorithm, the metric for the shortest path route searching is defined as follows.

𝑐 I = 𝑢 I • 𝑈 I (21)
Here as shown in Fig. 2, 𝑢 I is the capacity utilization or load on link l, which is defined as the ratio of the capacity used to the total capacity of the link. 𝑈 I is the unavailability of link l, which jointly considers the availability of the source node of the link and the availability of the link itself and is defined as

𝑈 I = 1 -𝐴 @ • 𝐴 I (22)
where, as shown in Fig. 2, 𝐴 @ is the availability of the source node of the link and 𝐴 I is the availability of the link itself. For a path traversing k links, we have the following approximation when the unavailability of each link is very small.

𝑈 G ≈ 𝑈 1 + 𝑈 9 + ⋯ + 𝑈 C (23)
where 𝑈 C is the unavailability of the k th link, calculated by (22). Therefore, using (21) as a metric to search for the shortest route is essentially to minimize the unavailability of a found route, weighted by the traffic load on each of the traversed links. As such, the found route can simultaneously balance its traffic load and maximize its availability, thereby achieving efficient provisioning performance.

Based on the above route-searching metric, we next present the detail of the Heu_load algorithm.

Algorithm Heu_Load

Step 1

For a slice request s, map its virtual nodes onto corresponding physical nodes, and judge whether the remaining C/S capacity of each mapped physical node is sufficient to satisfy the demand of the virtual node. If not, fail to provision the slice and stop; otherwise, move to the next step.

Step 2

For each virtual link in s, try to employ the shortest path algorithm to establish the virtual link along physical links with sufficient remaining capacity. The algorithm uses the metric in (21) as the cost of each physical link l for shortest path searching. Step 3

Repeat Step 2 until either all the virtual links in slice s are established or any one of the virtual links cannot be established due to the lack of link capacity. For the former, move to the next step; for the latter, fail to provision the slice and stop. Step 4 Compute the availability of slice s; if its availability is no less than 0.99999, the slice is provisioned successfully; otherwise, fail to provision the slice and stop. The overall computational complexity of the proposed algorithm is at the level of 𝑂(‖𝑽 𝒔 ‖ • (‖𝑵‖ + ‖𝑷‖) 9 ), where ‖•‖ finds the size of the set. Although straightforward, the algorithm is efficient to jointly consider both the capacity utilization and the unavailability of each physical link, which can balance the traffic load of the system and maximize the availability of each provisioned slice simultaneously.

Simulations and Performance Analyses

We use Fig. 1 and Fig. 3 as our test networks for the following performance evaluation. Fig. 1 consists of two PONs with 10 ONU-BSs, and 2 BSs function as relay to connect the two PONs, between which there are 22 microwave links. Fig. 2 contains 66 ONU-BSs and 9 BSs, placed on a real geographic information system (GIS) map. These ONU-BSs and BSs are shown to be clustered into 5 PONs. Note that for the sake of clarity, we only draw representative links in Fig. 2. The system parameters for the simulations are as follows. We set 𝜆 I , 𝜆 K , 𝜆 D , and 𝜆 G to be 200 FIT/km, 2000 FIT/km, 20 FIT, and 2 FIT, respectively. We also set the MTTRs of a fiber link, a microwave link, a BS node, and an OLT to be 6, 3, 2, and 1 hours, respectively. For each slice, different numbers N of virtual nodes (ranging from 4 to half of the total number of physical nodes) and virtual links (ranging from N to 1.5×N) are randomly generated, and each virtual link in a slice requests for a random bandwidth within the range of [50, 100] Mb/s. The maximum transmission capacity of each PON is assumed to be 10 Gb/s. The maximum transmission distance of a microwave link is 20 km, and its actual transmission capacity depends on its distance. Specifically, for a distance shorter than 10 km, the transmission capacity is assumed to be 3 Gb/s. For a distance (d) between 10~20 km, the transmission capacity is estimated as 3.6-0.06×d Gb/s. The number of microwave links established from/to each physical node is at the most 4. The C/S capacity at each physical node is limited to 100 VMs and each slice node needs 4 VMs. Based on these parameters, we ran simulations to show the following results.

Fig. 4 shows the results of the small network. Specifically, Fig. 4(a) shows the number of availability-guaranteed slices provisioned. With an increasing number of slices requested, the maximum number of slices provisioned increases accordingly, but is eventually saturated when the number of slices requested exceeds a certain threshold. This is because of the limited communication and C/S resources in a physical system. Whenever the physical resources are exhausted, no more slices can be provisioned. In addition, the Heu_load algorithm can provision more slices than that of the Heu_length algorithm. The Heu_load algorithm performs closer to the ILP model. When the number of slices requested is small, they perform similarly and only when the number of slices requested becomes larger that they perform differently. This is because of the extra load-balancing effort by the Heu_load algorithm. The Heu_length algorithm uses the route that has the maximum availability to establish a virtual link, which however ignores the impact of unbalanced load in a network, leading to the blocking of many slices due to insufficient capacity. In contrast, the Heu_load algorithm can balance both the aspects, and therefore demonstrates more efficiency in availability-guaranteed slice provisioning. Fig. 4(b) shows how the C/S capacity at each physical node affects the number of slices provisioned when there are 50 slices to be provisioned in the small network. With an increasing C/S capacity at each physical node, the maximum number of slices provisioned increases, and reaches a saturation level when the C/S capacity exceeds a threshold. This is because, before the threshold, the availability of VMs is more critical in limiting the success of slice provisioning, whereas after the threshold, with sufficient VMs, the link capacity of the system starts to play a more critical role. Again, in Fig. 4(b), we observe that the Heu_load algorithm is efficient to perform closer to the ILP model and outperforms the Heu_length algorithm.

Similar results were obtained for the larger test network shown in Fig. 5. Here due to the computational intractability, we do not provide the result of the ILP model, but show the results of the two heuristic algorithms. We can see that the Heu_load algorithm is more efficient to outperform the Heu_length algorithm to provision more availability-guaranteed slices. This is again attributed to the load-balancing effort made by the Heu_load algorithm.

Conclusion

We maximize the number of availability-guaranteed slices provisioned in a sliceable WOBAN that supports MEC. By considering different failure scenarios, a new definition of availability is made for a slice that functions only partially. We formulate the slice provisioning problem using an ILP model, and also develop two heuristic algorithms based on different link cost metrics. Simulation studies show the efficiency of the proposed heuristic algorithm that jointly considers capacity utilization and unavailability of a physical link when provisioning availability-guaranteed slices.

Fig. 1 .

 1 Fig. 1. Example of a sliceable WOBAN [10].

Fig. 2 .

 2 Fig. 2. The link metric calculation.

Fig. 3 .

 3 Fig. 3. Test network 2 in a GIS map [10].

  Number of slices provisioned. (b) Impact of C/S capacity at each physical node.

Fig. 4 .

 4 Fig. 4. Results of the small network.

  (a) Number of slices provisioned. (b) Impact of C/S capacity at each physical node.

Fig. 5 .

 5 Fig. 5. Results of the larger network.

Acknowledgement

This work was supported by National Natural Science Foundation of China (NSFC) (61671313) and the Project of Suzhou Key Laboratory of "Advanced Optical Communication Networks."

of the physical link l. 𝐴 𝑠 : The availability of the source node s. 𝐴 𝑙 : The availability of the physical link l. 𝑢 𝑙 : The capacity utilization of the physical link l. 𝑐 𝑢𝑠𝑒𝑑 : The used capacity of the physical link l.


Nikos Terzenidis

Miltiadis Moralis-Pegios

Stelios Pitris

Konstantinos Vyrsokinos

Nikos Pleros

Dual-layer locality-aware optical interconnection architecture for latency-critical resource disaggregation environments

Keywords: Silicon-photonics, Optical switch, Interconnection architecture, Disaggregated data center, Traffic locality

Significant research efforts, both industrial and academic, have been committed in the direction of Rack-scale computing through resource disaggregation, that aims to increase resource utilization at a reduced energy and cost envelope. However, the realization of resource disaggregation necessitates an underlying network infrastructure that can compete with a challenging set of requirements including low-latency performance and high-port count connectivity, as well as high data-rate operation. At the same time, it is crucial for the interconnection architecture to be able to accommodate efficient delivery of traffic with different locality characteristics. We propose a dual-layer locality-aware optical interconnection architecture for disaggregated Data Centers by combining the STREAMS silicon-based on-board communication paradigm with the disaggregation-oriented Hipoλaos high-port count switch. Simulation evaluation of a 256-node disaggregated system, comprising 32 optically-interconnected 8socket boards, revealed up to 100% throughput and mean, p99 latencies not higher than 335nsec and 610nsec, respectively, when a 50:50 ratio between onand off-board traffic is employed. Evaluation of the same layout with 75:25 on-/off-board traffic yields even lower mean and p99 latency at 210ns and 553ns, respectively.

Introduction

The ever-increasing energy consumption of Data Centers (DCs), projected to rise to 3% of the global electricity demand by 2020 [START_REF] Jones | How to stop data centres from gobbling up the world's electricity[END_REF], along with the huge waste of resources, that is observed in traditional DCs and may reach up to 50% [START_REF] Di | Characterizing Cloud Applications on a Google Data Center[END_REF]- [START_REF] Reiss | Heterogeneity and dynamicity of clouds at scale[END_REF], have forced DC operators to invest in solutions that will considerably improve energy efficiency. In this context, resource disaggregation in computing and network architectures is under heavy research [START_REF]Intel® Rack Scale Design[END_REF]- [START_REF] Bielski | dReDBox: Materializing a full-stack rack-scale system prototype of a next-generation disaggregated datacenter. 2018 Design[END_REF], as a groundbreaking innovation that could amortize the energy and cost impact caused by the vast diversity in resource demand of emerging DC workloads [START_REF]Tencent Explores Datacenter Resource Pooling Using Intel® Rack Scale Architecture (In-tel® RSA)[END_REF]. This architectural shift breaks the tight co-integration of CPU, memory and storage resources from a single server board, towards disaggregated systems with multiple resources organized in trays and synergized via the DC network. The first promising results of a full-fledged CPU-memory disaggregated prototype, from the EU-funded project dRedBox, suggest an important decrease in Total Cost of Ownership (TCO) [START_REF] Bielski | dReDBox: Materializing a full-stack rack-scale system prototype of a next-generation disaggregated datacenter. 2018 Design[END_REF], while the deployment of partially-disaggregated servers in Intel's DCs contributed to an impressive power usage effectiveness (PuE) rating of 1.06 [START_REF]Disaggregated Servers Drive Data Center Efficiency and Innovation[END_REF]. However, resource disaggregation, by breaking apart the critical CPU-to-memory path, introduces a challenging set of requirements in the underlying network infrastructure [START_REF] Gao | Network requirements for resource disaggregation[END_REF], that has to support low latency and high throughput communication, while providing connectivity to an increased number of nodes. At the same time, it is crucial for the interconnection architecture to be able to accommodate efficient unicast and multicast traffic delivery with different locality characteristics. To this end, recent studies [START_REF] Roy | Inside the Social Network's (Datacenter) Network[END_REF]- [START_REF] Kandula | The nature of data center traffic[END_REF] have indicated heavy traffic exchange within the boundaries of a Rack, that can be observed through a variety of emerging DC workloads, while a number of applications span their communication capacity through the entire network hierarchy [START_REF] Roy | Inside the Social Network's (Datacenter) Network[END_REF], requiring all-to-all connectivity. The transition to a disaggregation paradigm endorses this type of mixed communication profile and effectively narrows down the locality pattern to board-level, where for example computing resources are synergized in homogeneous pools exhibiting highly localized traffic, while requiring also connectivity with the memory or storage pools located in other trays of the system.

During the first demonstrations of disaggregated systems [START_REF] Bielski | dReDBox: Materializing a full-stack rack-scale system prototype of a next-generation disaggregated datacenter. 2018 Design[END_REF] optical circuit switches (OCS) have been employed to provide rack-level connectivity between resource bricks residing in different trays, due to their high-radix, scaling to hundreds of ports, along with their datarate-transparent operation. However, currently available OCS solutions based either on 3D Micro Electromechanical Systems (MEMS) [START_REF] Series | CALIENT Technologies[END_REF]- [START_REF]Glimmerglass Intelligent Optical Systems[END_REF] or piezoelectric beam steering technology [START_REF]384 port Software-Defined Optical Circuit Switch[END_REF] come at the cost of ms switching time values, that effectively limit their employment as slow reconfigurable backplanes [START_REF] Chen | Hardware Programmable Network Function Service Chain on Optical Rack-Scale Data Centers[END_REF]. To this end, we have recently demonstrated the Hipoλaos optical packet switch (OPS) architecture [START_REF] Terzenidis | High-port low-latency optical switch architecture with optical feed-forward buffering for 256-node disaggregated data centers[END_REF]- [START_REF] Terzenidis | Multicasting in a High-Port Sub-μsec Latency Hipoλaos Optical Packet Switch[END_REF], that provides low-latency connectivity between a high number of ports, while at the same time enabling dynamic switching operation with packet granularity. Moreover, Hipoλaos OPS offers up-to 95% throughput for unicast traffic when interconnecting 1024 nodes located in 32 different trays [START_REF] Moralis-Pegios | A 1024-Port Optical Uni-and Multicast Packet Switch Fabric[END_REF], enabling this way efficient communication through the whole Rack hierarchy.

Moving on to the next DC hierarchy layer, the tray, electrical switching solutions have been employed in the first disaggregated prototypes to provide on-board connectivity, following the established paradigm of interconnection architectures for multisocket boards (MSB), that are currently dominated by electrical point-to-point (P2P) links. While P2P interconnects, like Intel QPI [START_REF]An Introduction to the Intel® QuickPath Interconnect[END_REF] and AMD Infinity fabric, can definitely offer low latency and high bandwidth communication, their scalability is typically limited to 4 endpoints, before requiring extra latency-inducing hops or active switch-based solutions like Oracle Bixby [START_REF] Wicki | Bixby: The scalability and coherence directory ASIC in Oracle's highly scalable enterprise systems[END_REF] or PCIe switches. Recent advances on board-compatible optical interfaces highlight the significant throughput and delay improvements that can be released through optically-interconnected blade technologies [START_REF] Maniotis | Applica-tion-Oriented On-Board Optical Technologies for HPCs[END_REF], paving the way for their employment in high-density MSB scenarios. To this end, we have demonstrated, in the context of STREAMS project [START_REF] Kanellos | WDM mid-board optics for chip-to-chip wavelength routing interconnects in the H2020 ICT-STREAMS[END_REF], a Silicon-photonicsbased interconnection scheme for up to 40 Gb/s chip-to-chip communication [START_REF] Pitris | A 40 Gb/s Chipto-Chip Interconnect for 8-Socket Direct Connectivity Using Integrated Photonics[END_REF] using an integrated Ring-Modulator (RM) transmitter (Tx), an 8×8 Arrayed Waveguide Grating Router (AWGR)-based routing circuitry and a co-packaged InP-based photodiode (PD) and Transimpedance Amplifier (TIA) receiver (Rx). The STREAMS architecture is able to provide high-bandwidth communication to 8 on-board nodes, while the AWGR-based routing ensures ultra-low latency and efficient multicast/broadcast traffic delivery encompassing the requirements of coherency-induced multi-and broadcasting traffic patterns.

In this paper we combine the STREAMS silicon-based on-board interconnection architecture with the disaggregation-oriented Hipoλaos high-port count switch, in a duallayer locality-aware Rack interconnection scheme that efficiently accommodates the need for transparent on-board local traffic forwarding in a disaggregated environment with hundreds of nodes. We evaluate via an Omnet++ simulation analysis, this novel rack configuration with 256 disaggregated nodes using a number of 32 optically-interconnected 8-socket MSBs. This 256-socket setup can take advantage of traffic localization techniques towards low-latency workload execution, forming a powerful disaggregated rack-scale computing scheme with mean and p99 latencies not higher than 335nsec and 610nsec, respectively, when a 50:50 ratio between on-and off-board traffic is employed. Finally, evaluation of the same system with 75:25 on-:off-board traffic yields even lower mean and p99 latency at 210ns and 553ns, respectively.

2

Hipoλaos and STREAMS Optical Interconnects

Hipoλaos Rack-level optical switch architecture

Hipoλaos (High port λ routed all optical switch) manages to combine low latency and high-throughput performance into high-port count configurations, through a hybrid scheme exploiting Spanke switching and wavelength routing. The Hipoλaos switch differentiates from alternative OPS layouts by incorporating the multi-lambda routing capabilities of AWGRs, along with careful optimizations in the different stages of the Spanke architecture, that can be classified into four main categories/features: (i) Distributed control: The Hipoλaos architecture overcomes the scalability limitations of Spanke designs, towards high-port count layouts, by distributing the control and switching functions in small clusters, named as Planes. Moreover, this distributed nature of the architecture minimizes the computational time associated with forwarding and scheduling, contributing this way to lower total latency of the switch fabric.

(ii) Feed-forward buffering: The adoption of small-scale optical buffering [START_REF] Moralis-Pegios | On-Chip SOI Delay Line Bank for Optical Buffers and Time Slot Interchangers[END_REF] enables the realization of high-throughput performance while at the same time reducing latency by avoiding optoelectronic buffering and the associated Optical/Electrical/Optical conversions.

(iii) Advanced Wavelength Conversion schemes: Wavelength converters (WC) on the different stages of the Spanke layout utilize the differentially biasing scheme [START_REF] Spyropoulou | 40 Gb/s NRZ Wavelength Conversion Using a Differentially-Biased SOA-MZI: Theory and Experiment[END_REF], that has been shown to operate successfully with up to 40Gb/s NRZ signals, fulfilling the requirement for high datarates.

(iv) Multi-wavelength routing: The architecture utilizes the cyclic routing properties of AWGRs in order to extend the switch radix through a collision-less WDM routing mechanism, that ensures non-blocking forwarding of the different packets to the desired destination node. Moreover, it enables the realization of multicast functionality building upon the proven efficiency of AWGR devices in multicast operations [START_REF] Pitris | O-band Energy-efficient Broadcastfriendly Interconnection Scheme with SiPho Mach-Zehnder Modulator (MZM) & Arrayed Waveguide Grating Router (AWGR)[END_REF]. The feasibility of the Hipoλaos architecture has been validated through a prototype experimental evaluation following the design principles of the 256-port layout [START_REF] Terzenidis | High-port low-latency optical switch architecture with optical feed-forward buffering for 256-node disaggregated data centers[END_REF], while its network performance characteristics have been evaluated through a variety of unicast traffic scenarios [START_REF] Terzenidis | High-Port and Low-Latency Optical Switches for Disaggregated Data Centers: The Hipoλaos Switch Architecture[END_REF] revealing a high throughput value of >85%, for up to 100% loads, along with 605nsec latency, even for 2 packet-size optical buffers. An actual photo of the experimental prototype is depicted in the right inset of Fig. 3. A scalability analysis of the Hipoλaos architecture, considering also the main limiting factors, has been presented in [START_REF] Terzenidis | High-Port and Low-Latency Optical Switches for Disaggregated Data Centers: The Hipoλaos Switch Architecture[END_REF], concluding to an attainable port-count of at least 1024-ports, with the experimental evaluation in unicast and multicast operational mode presented in [START_REF] Moralis-Pegios | A 1024-Port Optical Uni-and Multicast Packet Switch Fabric[END_REF].

STREAMS silicon-photonics board-level interconnect

The European H2020 project ICT-STREAMS is currently attempting to deploy the necessary silicon photonic and electro-optical PCB technology toolkit for realizing the AWGR-based MSB interconnect benefits in the O-band and at data rates up to 50Gb/s [START_REF] Kanellos | WDM mid-board optics for chip-to-chip wavelength routing interconnects in the H2020 ICT-STREAMS[END_REF], [START_REF] Alexoudi | Optics in Computing: From Photonic Network-on-Chip to Chip-to-Chip Inter-connects and Disintegrated Architectures[END_REF]. It aims to exploit wavelength division multiplexing (WDM) Silicon photonics transceiver technology at the chip edge as the socket interface and a board-pluggable O-band silicon-based AWGR as the passive routing element, as shown in a generic Nsocket architecture depicted in Fig. 2. Each socket is electrically connected to a WDMenabled Tx optical engine equipped with N-1 laser diodes (LD), each one operating at a different wavelength. Every LD feeds a different Ring Modulator (RM) to imprint the electrical data sent from the socket to each one of the N-1 wavelengths, so that the Tx engine comprises finally N-1 RMs along with their respective RM drivers (DR). All RMs are implemented on the same optical bus to produce the WDM-encoded data stream of each socket. The data stream generated by each socket enters the input port of the AWGR and is forwarded to the respective destination output that is dictated by the carrier wavelength and the cyclic-frequency routing properties of the AWGR [START_REF] Leijtens | Arrayed Waveguide Gratings[END_REF]. In this way, every socket can forward data to any of the remaining 7 sockets by simply modulating its electrical data onto a different wavelength via the respective RM, allowing direct single-hop communication between all sockets through passive wavelengthrouting. At every Rx engine, the incoming WDM-encoded data stream gets demultiplexed with a 1:(N-1) optical demultiplexer (DEMUX), so that every wavelength is received by a distinct PD. Each PD is connected to a transimpedance amplifier (TIA) that provides the socket with the respective electrical signaling. This flat-topology AWGR-based interconnect scheme requires a higher number of transceivers compared to any intermediate switch solution, but this is exactly the feature that allows to combine WDM with AWGR's cyclic frequency characteristics towards enabling single-hop communication and retaining the lowest possible latency. Link capacity can be increased in this case by residing on channel bonding through bit-parallel schemes, as already reported in [START_REF] Grani | Bit-Parallel All-to-All and Flexible AWGRbased Optical Interconnects[END_REF], by using AWGR designs for waveband instead of single wavelength routing. Utilizing an 8×8 AWGR, the optically-enabled MSB can allow single-hop all-to-all interconnection between 8 sockets, while scaling the AWGR to 16×16 layouts can yield single-hop communication even between 16 sockets, effectively turning current "glued" into "glueless" designs. The ICT-STREAMS on-board MSB aims to incorporate 50GHz single-mode O-band electro-optical PCBs [START_REF] Lamprecht | EOCB-Platform for Integrated Photonic Chips Direct-on-Board Assembly within Tb/s Applications[END_REF], relying on the adiabatic coupling approach between silicon and polymer waveguides [START_REF] Dangel | Polymer Waveguides Enabling Scalable Low-Loss Adiabatic Optical Coupling for Silicon Photonics[END_REF] for low-loss interfacing of the Silicon-Photonics transceiver and AWGR chips with the EO-PCB.

The first 40Gb/s experimental demonstration of the fiber-interconnected integrated photonic building blocks when performing in the AWGR-based 8-socket MSB architecture, presenting the 40Gb/s experimental results have been reported in [START_REF] Pitris | A 40 Gb/s Chipto-Chip Interconnect for 8-Socket Direct Connectivity Using Integrated Photonics[END_REF]. The energy efficiency of the proposed 40 Gb/s C2C photonic link is estimated at 24 pJ/bit, but can dramatically go down to 5.95 pJ/bit when transferring the demonstrated fiber-pigtailed layout into an on-board assembled configuration and assuming a 10% wall-plug efficiency for the external laser. This indicates that the on-board version has the credentials to lead to 63.3% reduction in energy compared to the 16.2 pJ/bit link energy efficiency of Intel QPI [START_REF] Gough | Energy efficient servers: blueprints for data center optimization[END_REF].

Dual-layer Locality-aware optical interconnection architecture

Fig. 3 presents a schematic illustration of a 256-node DC system comprising 32 optically-enabled STREAMS boards, with every board incorporating 8 network nodes.

Every node in the proposed dual-layer network hierarchy is connected via different optical links to an on-board 8x8 AWGR, serving as the intra-board routing infrastructure, as well as to a Hipoλaos-based 256 port switch, providing inter-board all-to-all connectivity. The internal node architecture is depicted in the left inset of Fig. 3, where a CPU, for example, can communicate with any of the remaining 7 nodes of the board by utilizing links #1 to #7 that effectively forward data via the underlying silicon photonics Tx engine. The WDM-encoded data stream, comprising seven lambdas, is forwarded to the on-board AWGR device where every wavelength channel is finally delivered to a different end node. This first layer of switching can ensure maximum throughput of on-board traffic, being in agreement with the requirement for transparent localized traffic forwarding, while the latency associated with header processing and scheduling is eliminated, since the routing decision is performed in the source node by simply selecting the appropriate link(s). The second layer in the switching topology can be accessed through link #8, that forwards inter-board traffic, via a fixed-wavelength optical data stream, to the Hipoλaos switch. The internal architecture of the 256-port Hipoλaos layout, that has been described in detail in [START_REF] Terzenidis | High-port low-latency optical switch architecture with optical feed-forward buffering for 256-node disaggregated data centers[END_REF], comprises 16 switch Planes with every Plane aggregating traffic from 16 nodes. Due to the mismatch between the number of nodes per board and the number of ports per Plane, the input port allocation per switch plane is performed so that Node#i, 1 ≤ i ≤ 8, from the odd-numbered boards#j, j=1,3,..,31, connects to the input#k, k=(j+1)/2, of Plane#l, l=i, denoted as input (l,k) of the switch. Moreover, Nodes#i, 1 ≤ i ≤ 8, from the even-numbered boards#j, j=2,4,..,32, connect to the input#k, k=j/2, of Plane#l, l=8+i. The proposed port-allocation scheme groups into the respective contention resolution stages of the switch packets from 2 adjacent boards, that in conjunction with the on-board switching layer ensures minimum contention between the different packets. It should be noted that every node can accommodate either computing resources, as illustrated on the example of Fig. 3, as well as memory, storage and accelerator resources. Having already demonstrated the performance credentials of each constituent interconnection scheme in [START_REF] Terzenidis | High-port low-latency optical switch architecture with optical feed-forward buffering for 256-node disaggregated data centers[END_REF] and [START_REF] Terzenidis | High-Port and Low-Latency Optical Switches for Disaggregated Data Centers: The Hipoλaos Switch Architecture[END_REF], we have proceeded with the evaluation of the network throughput and latency performance in a DC system incorporating the proposed dual-layer interconnection architecture. A simulation analysis has been performed for the 256-node system illustrated in Fig. 3, using the Omnet++ discrete event platform. A synchronous slotted network operation has been modelled where the packets are generated at predefined packet-slots, each one lasting for 57.6ns. The traffic profile was customized to distribute a certain percentage of the total traffic generated by every node, uniformly to nodes of the same board (intra-board traffic), while the rest of the traffic was uniformly distributed to nodes from the other 31 boards (inter-board traffic). In order to offer a thorough evaluation of the architecture's performance, in terms of latency, both mean packet delay, as well as p99 delay metrics were collected by the simulation. The switch port allocation to the network nodes was performed according to the procedure described in the previous paragraph and illustrated in the layout of Fig. 3.

The modelled DC system featured node-to-switch and node-to-AWGR channel datarate of 10 Gb/s, along with fixed size packet-length of 72 bytes, comprising 8-bytes for header, synchronization and guard-band requirements and 64 bytes data payload, matching the size of a single cache-line transfer. Regarding the Hipoλaos processing latency, it was modelled to 456ns in accordance with the experimental results [START_REF] Terzenidis | High-port low-latency optical switch architecture with optical feed-forward buffering for 256-node disaggregated data centers[END_REF], while the propagation latency for the various optical components of the switch (fibers, amplifiers, AWGRs), excluding the optical delay lines, was modelled to be 35ns.

In order to perform a versatile evaluation of the proposed architecture under different traffic locality patterns, we have considered in our analysis two different cases for the percentage of the intra-/inter-board traffic; 50/50 and 75/25. Performance has been evaluated as a function of the available packet-buffers in the Hipoλaos switch, with the number of buffers ranging for 0 to 4 and corresponding to the maximum number of buffers experimentally demonstrated in [START_REF] Terzenidis | High-Port and Low-Latency Optical Switches for Disaggregated Data Centers: The Hipoλaos Switch Architecture[END_REF]. 4(a) presents the respective throughput versus the offered load results, concerning the total network traffic (both intra-and inter-board) for different numbers of buffers per Hipoλaos DLB. As expected, throughput increases almost linearly with increasing buffer size, approaching 100% for 100% offered load as long as the buffer size equals to more than 2 packet slots. Figure 4(b) presents the mean packet delay versus the offered load results, showing that latency ranges between 295ns and 330ns for a buffer size between 0 and 2 packet slots and for loads until 100%. Mean latency increases slightly as the buffer size increases reaching a maximum value of 335ns for a buffer size of 4 packet slots where throughput reaches also its maximum value. Figure 4(c) presents the p99 delay results vs. the offered load, revealing a p99 value of 610ns for maximum load and 4 buffers per DLB. As can be observed, the p99 delay metrics perform a step-wise "jump" as contention occurs due to the fact that packets are forwarded to longer DLB buffers that introduce delays in packet duration granularity. It is important to note that the only point of congestion in the architecture was identified at the Hipoλaos switch, since the intra-board AWGR switching scheme is able to offer 100% throughput and minimum latency values originating just from the signal's propagation delay.

Fig. 4(d) to (f) present the simulation results for the case of 75/25 intra-/inter-board traffic distribution. As expected, throughput is slightly higher, reaching 100% in all cases, due to the fact that a lower percentage of traffic is headed towards the Hipoλaos switch, where congestion occurs. At the same time mean packet latency is decreased to 210ns, while p99 latency now presents a maximum value of 550ns, as less delay lines have to be utilized in the Hipoλaos DLB blocks.

The vital information that can be easily extracted from Fig. 4(b)-(c) and Fig. 4(e)-(f), is that the proposed dual-layer switching topology does not induce any additional latency compared to the conventional Hipoλaos architecture [START_REF] Terzenidis | High-port low-latency optical switch architecture with optical feed-forward buffering for 256-node disaggregated data centers[END_REF], but rather decreases the mean and p99 packet latency, due to the fact that the 2 switching layers operate in a parallel and functionally isolated manner. With sub-μsec latency considered as the main performance target for current memory disaggregated systems [START_REF] Gao | Network requirements for resource disaggregation[END_REF], the mean and p99 latency values of this novel Hipoλaos-STREAMS-based architecture with clustered optically-enabled 8-Socket MSBs reveals an excellent potential for a practical interconnect solution that can bring latency down to just a few 100's of nanosecond. Allowing on-board nodes to cluster in single-hop configurations over AWGR-based interconnects can yield minimized latency when combined with proper workload allocation for strengthening board-level traffic localization, while off-board traffic benefits from the latency-optimized dynamic switch characteristics of the Hipoλaos design.

Conclusion

The emergence of resource disaggregation in DC architectures is imposing stringent requirements on the interconnection architecture that has to support low-latency, highthroughput and high-radix connectivity, while at the same time accommodating efficient delivery of traffic with different locality characteristics. To this end we have demonstrated a dual-layer locality-aware optical interconnection architecture by combining the ICT-STREAMS silicon-photonics on-board communication paradigm with the intra-DC Hipoλaos high-port count switch. Simulation analysis of a 256-node disaggregated system, comprising 32 optically-interconnected 8-socket boards, revealed up to 100% throughput and mean, p99 latencies not higher than 335nsec and 610nsec, respectively, when a 50:50 ratio between on-and off-board traffic is employed. Finally, this layout could in principle form the basis for replacing the massive QPI "island" interconnection supported by a number of switch technologies like Bixby's [START_REF] Wicki | Bixby: The scalability and coherence directory ASIC in Oracle's highly scalable enterprise systems[END_REF] and PCI express, yielding a powerful network of cache-coherent islands at a maximum p99 latency value just above 600nsec even when a balanced 50/50 traffic locality pattern is followed.

Fig. 1 .

 1 Fig. 1. (a) N×N Spanke switch architecture, (b) Schematic illustration of a N 2 -node DC, organized in #N Rack-Trays with #N nodes per tray and interconnected via a N 2 ×N 2 ToR Hipoλaos switch Fig. 1(b) depicts a schematic illustration of the Hipoλaos OPS architecture, configured in a N2×N2 layout, interconnecting #N Rack trays with #N computing nodes in every tray. The switch is organized in #N Planes that are interconnected to #N AWGR devices. On the ingress path, every node communicates with a specific Plane over a different fiber link, while the Plane's role is to aggregate traffic from #N input ports and forward it via a BS scheme, with every 1:N splitting node corresponding to the 1:N switches employed in the Spanke architecture, as depicted in Fig. 1(a). The N:1 switches at the outputs of the Spanke design are modified to incorporate an Optical Delay-Line Bank (DLB), forming this way an optical contention resolution stage comprising #N DLBs. Packets leaving the contention resolution stage are finally delivered to the destination node after passing through a wavelength routing stage comprising tunable WCs and cyclic routing AWGRs.The feasibility of the Hipoλaos architecture has been validated through a prototype experimental evaluation following the design principles of the 256-port layout[START_REF] Terzenidis | High-port low-latency optical switch architecture with optical feed-forward buffering for 256-node disaggregated data centers[END_REF], while its network performance characteristics have been evaluated through a variety of unicast traffic scenarios[START_REF] Terzenidis | High-Port and Low-Latency Optical Switches for Disaggregated Data Centers: The Hipoλaos Switch Architecture[END_REF] revealing a high throughput value of >85%, for up to 100% loads, along with 605nsec latency, even for 2 packet-size optical buffers. An actual photo of the experimental prototype is depicted in the right inset of Fig.3. A scalability analysis of the Hipoλaos architecture, considering also the main limiting factors, has been presented in[START_REF] Terzenidis | High-Port and Low-Latency Optical Switches for Disaggregated Data Centers: The Hipoλaos Switch Architecture[END_REF], concluding to an attainable port-count of at least 1024-ports, with the experimental evaluation in unicast and multicast operational mode presented in[START_REF] Moralis-Pegios | A 1024-Port Optical Uni-and Multicast Packet Switch Fabric[END_REF].

Fig. 2 .

 2 Fig. 2. STREAMS optical N×N AWGR-based interconnection concept for MSB connectivity exploiting WDM-enabled Tx/Rx engines.

Fig. 3 .

 3 Fig. 3. Illustration of a locality-aware Rack interconnection scheme employing 32 Streams boards, with 8 nodes each, interconnected to a 256x256 Hipoλaos switch. On the left inset, the internal node architecture is presented, while on the right an actual photo of the Hipoλaos experimental prototype is presented.

Fig. 4 .

 4 Fig. 4. Simulation results for different number of buffers per DLB (a) Throughput -50/50, (b) Mean latency -50/50, (c) P99 latency -50/50, (d) Throughput -75/25, (e) Mean latency -75/25, (f) P99 latency -75/25Fig.4(a) to (c) present the simulation results for the case of 50/50 intra-/inter-board traffic distribution. Figure4(a) presents the respective throughput versus the offered load results, concerning the total network traffic (both intra-and inter-board) for different numbers of buffers per Hipoλaos DLB. As expected, throughput increases almost linearly with increasing buffer size, approaching 100% for 100% offered load as long as the buffer size equals to more than 2 packet slots. Figure4(b) presents the mean packet delay versus the offered load results, showing that latency ranges between 295ns and 330ns for a buffer size between 0 and 2 packet slots and for loads until 100%. Mean latency increases slightly as the buffer size increases reaching a maximum value of 335ns for a buffer size of 4 packet slots where throughput reaches also its maximum value. Figure4(c) presents the p99 delay results vs. the offered load, revealing a p99 value of 610ns for maximum load and 4 buffers per DLB. As can be observed, the p99 delay metrics perform a step-wise "jump" as contention occurs due to the fact that packets are forwarded to longer DLB buffers that introduce delays in packet duration granularity. It is important to note that the only point of congestion in the architecture was identified at the Hipoλaos switch, since the intra-board AWGR switching scheme is able to offer 100% throughput and minimum latency values originating just from the signal's propagation delay.Fig.4(d) to (f) present the simulation results for the case of 75/25 intra-/inter-board traffic distribution. As expected, throughput is slightly higher, reaching 100% in all cases, due to the fact that a lower percentage of traffic is headed towards the Hipoλaos switch, where congestion occurs. At the same time mean packet latency is decreased to 210ns, while p99 latency now presents a maximum value of 550ns, as less delay lines have to be utilized in the Hipoλaos DLB blocks.

Figure

  Fig.4(a) to (c) present the simulation results for the case of 50/50 intra-/inter-board traffic distribution. Figure4(a) presents the respective throughput versus the offered load results, concerning the total network traffic (both intra-and inter-board) for different numbers of buffers per Hipoλaos DLB. As expected, throughput increases almost linearly with increasing buffer size, approaching 100% for 100% offered load as long as the buffer size equals to more than 2 packet slots. Figure4(b) presents the mean packet delay versus the offered load results, showing that latency ranges between 295ns and 330ns for a buffer size between 0 and 2 packet slots and for loads until 100%. Mean latency increases slightly as the buffer size increases reaching a maximum value of 335ns for a buffer size of 4 packet slots where throughput reaches also its maximum value. Figure4(c) presents the p99 delay results vs. the offered load, revealing a p99 value of 610ns for maximum load and 4 buffers per DLB. As can be observed, the p99 delay metrics perform a step-wise "jump" as contention occurs due to the fact that packets are forwarded to longer DLB buffers that introduce delays in packet duration granularity. It is important to note that the only point of congestion in the architecture was identified at the Hipoλaos switch, since the intra-board AWGR switching scheme is able to offer 100% throughput and minimum latency values originating just from the signal's propagation delay.Fig.4(d) to (f) present the simulation results for the case of 75/25 intra-/inter-board traffic distribution. As expected, throughput is slightly higher, reaching 100% in all cases, due to the fact that a lower percentage of traffic is headed towards the Hipoλaos switch, where congestion occurs. At the same time mean packet latency is decreased to 210ns, while p99 latency now presents a maximum value of 550ns, as less delay lines have to be utilized in the Hipoλaos DLB blocks.

Acknowledgments. This work has been partially supported by the European H2020 projects ICT-STREAMS (Contract No. 688172) and L3MATRIX (Contract No. 688544).