Open Access
Add to BibSonomy
Abstract
Enduring the rapidly growing demand for high data rates is the main challenge for the current network providers. Super passive optical network (Super-PON), a prominent next generation Ethernet PON (NG-EPON) candidate, can suffice this exponentially increasing data rate requirements. However, to appease such requirements, it employs many transceivers and increases the power-consumption of the network. In this work, we focus on reducing the carbon footprint of Super-PON and propose power-efficient dynamic bandwidth and wavelength allocation (DBWA) algorithms, namely best fit bin-packing sleep mode aware (BF-SMA) and updated BF-SMA (UBF-SMA). The proposed algorithms use SMA for bandwidth scheduling and different bin-packing techniques for wavelength allocation. In bin-packing, the number of available wavelengths and their efficient allocation is based on the network load. For restricting the number of available wavelengths, we can switch off the non-essential transceivers at the OLT, which also helps in maximizing the wavelength utilization and increasing the power efficiency. The simulation results show that in comparison to the state-of-the-art DBWA algorithms, the proposed algorithms improve the power efficiency and reduce the average delay of a Super-PON system. Furthermore, we use Jain’s fairness index to validate the fairness of the proposed DBWA algorithms.
© 2021 Optical Society of America under the terms of the OSA Open Access Publishing Agreement
1. Introduction
With the upcoming era of high-speed applications, complex technologies, cloud-based storage, the need for high bandwidth access systems has become indispensable. In this decade, the IP traffic is expected to grow three folds, and the number of networked gadgets per capita is predicted to be 3.5 by 2021 [1], [2]. This has triggered the development of technologies that meets these future demands. Furthermore, the current information communication technology (ICT) consumes $8\%$ of the world power consumption [3], and contributes approximately $2\%$ to the global CO2 emissions [4]. This has forced the government agencies and standard bodies to develop the power-efficient protocols to minimize the power consumption of ICT [5]. As a result, there is a recent boost in developing the power-efficient technologies, protocols, and devices that are envisioned to endure the ever-increasing bandwidth demand.
Next generation Ethernet passive optical network (NG-EPON) is one such prospective technology that is contemplated by the IEEE 802.3ca to meet these forthcoming stipulations [6]. NG-EPON is a fiber-to-the-everything (FTTx) technology that is envisioned to support a vast capacity of no less than 25 Gbps, the extended geographical coverage of more than 20 km, more clients ranging from 256 to 1024, and multiple wavelengths [5], [7]. Super-PON is an emerging proposal for NG-EPON because of its capability to provide these envisioned obligations and its compatibility with the legacy optical distribution networks (ODN) [8].
A typical Super-PON consists of the optical line terminal (OLT) at the central office (CO), and many optical network units (ONUs) at the customer premises. They are linked through optical passive splitters and fibers present at ODN. Super-PON architecture supports various symmetric and asymmetric downstream (i.e., from the OLT to ONU) and upstream (i.e., from the ONU to OLT) data rates such as 25/10G-EPON, 25/25G-EPON, 50/10G-EPON, 50/25G-EPON, and 50/50G-EPON [9]. To enable these higher bandwidths, several transmitters of EPON at different wavelengths are stacked together to form Super-PON, and this Super-PON requires a media access control (MAC) protocol suitable to IEEE developed standards. In the IEEE P802.3ca standard for Ethernet, the OLT transmits a GATE message (i.e., a control message) to the ONUs, and it contains a unique logical link identifier (LLID) and a transmission slot for the respective ONU. The respective ONU starts sending its data packets according to the allotted time slot on receiving this GATE message. These data packets are followed by a REPORT message that contains the ONU’s current buffer occupancy. The ONUs are statistically multiplexed to share the available resources in the upstream direction. Thus, in the upstream direction, commanding the packet transmission is more perplexing than the downstream direction where the message contains the ID of respective ONU. Furthermore, Super-PON employs four wavelengths that are shared dynamically among the ONUs. In such a network, overuse of a single wavelength may result in a notable increase in latency; while other wavelengths are underutilized or idle leading to the inequitable use of bandwidth [10]. Therefore, proposing the schemes that can manage both bandwidth and wavelength constructively are noteworthy.
Power savings in the legacy PONs is mainly possible by using different sleep modes at the ONUs. The sleep mode is standardized under the power-efficient framework of IEEE P1904.1 standard for service interoperability in Ethernet passive optical networks (SIEPON) [2]. In the sleep mode, the ONU’s transceivers are switched off according to the network load. Nevertheless, another significant attribute of Super-PON is its stacked architecture that offers the new possibilities of power savings at the OLT. The saving opportunities arrive in two ways: first by distributing the wavelengths dynamically among the optical network units (ONUs), and second by switching off the idle transceivers [11]. To enable these savings in the optical network, many power saving dynamic bandwidth and wavelength allocation (DBWA) algorithms have already been proposed in the literature [10], [12]–[16]. In [10], the authors propose a high priority first DBWA (HF-DBWA) scheme that employs service level agreement (SLA) based ONU’s priority assessment and bandwidth and wavelength allotment, while justifying the fair resource allocation among other ONUs. In [12], the authors propose a hybrid sleep mode aware (HSMA) scheme that uses the amalgamation of power savings due to the sleep mode with load dependent operation of transmitter and receivers at the OLT. The authors in [13] suggest the use of traffic-aware power-efficient scheme that considers the network load-based modularization of the OLT transceivers, and dynamically changes the ONUs’ polling sequence based on the packet emergence. The authors of [14] employ a software-defined network (SDN) based power saving scheme, where an SDN monitor at the OLT orchestrates bandwidth and wavelength allocation dynamically depending upon the network traffic. In [15], we propose the bin-packing sleep mode aware (BP-SMA) scheme that combines the power efficiency because of the sleep mode aware ONU and the first fit bin-packing dependent OLT transceivers. The authors in [16], propose a DBWA algorithm that uses a type of next fit bin-packing algorithm for the wavelength scheduling, and optimize the algorithm according to the network latency requirements. However, these techniques endure some issues such as the higher network latency, the higher complexity involved in predictions, unfair resource allocation, and improper utilization and switching of wavelengths.
In this paper, we propose novel DBWA algorithms, namely best fit bin-packing sleep mode aware (BF-SMA), and updated BF-SMA (UBF-SMA) that use the best fit bin-packing (BF-BP), and updated BF-BP (UBF-BP), respectively, for dynamically assigning the active wavelengths, and use the SMA algorithm for bandwidth allotment. BF-BP is a technique that has received lots of attention and is used to assign each object (present on the list) a unique bin (of unit size) in such a manner that the number of bins is minimized [17]. In our case, we use this BF-BP technique to assign every ONU (that are demanding different bandwidths) a unique wavelength such that the number of wavelengths used is minimized. This minimization not only results in efficient utilization of wavelengths but also improves the power savings in Super-PON. However, as the proposed algorithms are EPON based, they do not support frame fragmentation possible in the TWDM-PON case. Additionally, the proposed DBWA algorithms are offline in nature, i.e., it involves separate wavelength and bandwidth scheduling. In the offline approach, the OLT waits until it gets the full knowledge of all REPORT messages coming from the ONUs, and hence, takes the wavelength scheduling decision considering the bandwidth requirements of all ONUs [18], [19]. This consideration makes the wavelength scheduling scheme less expensive, less complex, and helps the OLT in making a fair wavelength allocation decision.
The main objective of our work is to propose power-efficient DBWA algorithms that inherent four important elements, namely low latency, low complexity, efficient wavelength utilization, and fairness. This is fulfilled in the following manner:
- • To lower the network latency that is affected by the unrestricted wavelength switching, we use the knowledge of available capacity on the previous cycle wavelength of the ONU. If this capacity can fulfill the ONU’s requirements again, then we do not change the wavelength. To further restrict the wavelength switching, we calculate the number of wavelengths to be assigned in the current wavelength allocation cycle beforehand. If this number is the same as in the previous cycle, we do not proceed with the periodic wavelength allocation process and continue with the previous phase assignments.
- • For reduced complexity we use the offline BF-BP algorithm for wavelength scheduling. This algorithm uses For and If-Else loops operators that are of very low complexity.
- • The offline BF-BP algorithm also ensures increased wavelength utilization efficiency. This algorithm keeps the list of the active wavelengths sequenced according to their available capacity, and the current fullest wavelength is assigned to the ONU that fits it [20].
- • Use of bin packing helps to induce fairness in the case where data packets have different packet size. Additionally, to prove that the proposed algorithms are fair, we consider the case of asymmetric traffic profile and use Jain’s fairness index for the validation.
2. Super-PON
A typical stacked Super-PON architecture that we envisaged for our IEEE MAC compliant DBWA techniques is given in Fig. 1. To serve high bandwidth requirements, we stack four 10G-EPONs. All these 10G-EPONs serve at different upstream and downstream wavelengths. We consider four O-band wavelengths for the downstream direction confining within 1356 to 1360 nm and four O-band wavelengths for the upstream direction confining within 1260 to 1280 nm. Additionally, due to the broadcasting nature of the downstream data, each ONU uses a tunable transmitter and receiver. This not only helps in transmitting and receiving data on the appropriate wavelengths but also reduces the inventory problems for the ONU [21].
Fig. 1. Typical Super-PON architecture (Abbreviations in the figure: AWG - Arrayed waveguide grating, WDM - Wavelength division multiplexing, OA - Optical amplifiers).
To coexist with the legacy PONs, Super-PON reuses power splitter. This use of power splitter slashes the establishment cost and induces flexibility in the wavelength scheduling [22]. Additionally, the use of an optical amplifier pre-amplifies the signal and uplifts the power budget. Moreover, the whole architecture is in tree topology, where the root is the CO, the leaves are the customer premises, and they are connected by optical fiber and power splitter present at the ODN. Additionally, we encapsulate the most relevant symbols that we consider in this work in Table 1.
Table 1. Notations used in the paper
3. Proposed power-efficient DBWA algorithm
Super-PON enables switching off the idle wavelengths that result in high utilization of the active wavelengths at the OLT and the bursty and slotted nature of the upstream and downstream transmission helps in exploiting the sleep modes at the ONUs. Since Super-PON requires the management of both bandwidth and wavelengths, its scheduling completes in two stages: wavelength minimization and allocation (WMA) and time slot allotment (TSA). Considering this, we propose two DBWA algorithms, namely BF-SMA and UBF-SMA. The algorithms utilize IEEE-based MAC and involve a separate time and wavelength scheduling. The idea is to use the BF-BP (or updated BF-BP) algorithm for WMA and the SMA algorithm for TSA.
The grouping of the ONUs on the same upstream and downstream wavelengths aid in the segmentation of Super-PON to the logical time division multiple access PON (TDMA-PON). We manage these TDMA cycles using an online algorithm named SMA [23]. In the SMA algorithm, the OLT communicates with the ONUs using the GATE message. This GATE message conveys two crucial information to the ONUs: the activity period and the sleep period. The ONU can receive and transmit data in the activity period and can sleep during the sleep period. This sleep period (denoted by $S_T(i)$ for $i^{th}$ cycle) can be calculated as (see Fig. 2) [23]
where $G_T(i)$ denotes the gate time of $i^{th}$ cycle, $T_s(i)$ denotes the transmission slot, and $T_o$ denotes the sleep overheads (i.e., the time epoch in switching the state of components from OFF to ON). Considering no error in the prediction of $T_s$, the sleep time percentage $S(\%)$ is given as The OLT considers the time that an ONU takes in waking up and adds it to the transmission time of the next GATE message. This ensures that the ONU is awake to receive the GATE message. The ONU receives a GATE message, after it wakes up and then tune to the operating wavelength (mentioned in the GATE message) for data transmission.Bin-packing (an NP-hard problem similar to WMA in Super-PON) involves packing an array of items within one bin. Every item carries a certain weight, and every bin has a unit capacity. Bin-packing aims to use the minimum possible bins and pack all the items such that none of the bins surpass its limit of unit capacity [24]. Furthermore, difficulty in finding the exact solution for NP-hard problems have resulted in focusing the research on bin-packing to the performance of heuristics. The research has led to the packing solutions that are as good as the optimal. One such most widely studied solution is BF-BP.
In the BF-BP algorithm, we process the items one by one. For every item, we pack the item in a bin that has the minimum residual capacity (also known as the tightest bin) and can fit the item [25]. If no such bin is found, then a new bin is created, and we pack the item in that bin [26], [27]. In the case of Super-PON, we propose using the BF-BP algorithm for WMA, where we pack the wavelengths (or bins) with the active ONUs (or items) and try to minimize the number of active wavelengths. To the best of our knowledge, the BF-BP algorithm is never used for an offline WMA. However, the BF-BP algorithm and our problem differ in some preliminaries. In the BF-BP algorithm, the number of bins is infinite, while in our case, the number of wavelengths is limited. Additionally, in the BF-BP algorithm, once an item is packed in a bin, it stays there forever, while in our case, the ONUs leave the wavelength, and these wavelengths are reused to pack new (or different) ONUs. How we adapt the BF-BP algorithm for our case is discussed with the proposed DBWA algorithms in the next subsections.
3.1 BF-SMA
To improve the power efficiency of Super-PON adhering to its latency constraint, we propose the BF-SMA algorithm. It employs an offline WMA scheduling, i.e., we assign wavelength to the ONUs after a certain interval of time (denoted as $T$). During this interval $T$, we scrutinize the data bits demand of the ONUs and use the collected data to calculate and assign the active wavelengths to the ONUs. The number of active wavelengths $(N_w)$ is calculated as
where $N_o$ denotes the number of active ONUs, $D_i$ denotes the sum of data bits requested by the $i^{th}$ ONU over $T$ interval, and $L_R$ denotes the line rate of each wavelength (in bits/sec). Hence, the number of active wavelengths depends only on the upstream data bits requirements of the ONUs. We consider the same number of wavelengths in the upstream and downstream direction. Now, we need to pack $N_o$ ONUs on $N_w$ wavelengths so that the wavelengths are efficiently utilized. To fulfil this aim, we propose the adaptation of the offline BF-BP algorithm and summarize it in Algorithm 1. At an interval of $T$, the OLT executes wavelength assignment operation by applying Algorithm 1. For this algorithm, we first sort all the ONUs according to their normalized network loads in the decreasing order and form an array (denoted by $\rho$) given as where $\rho _i$ is the normalized network load of $i^{th}$ ONU and is calculated as We sort the array in the decreasing order because it is a well-known fact that the offline BF-BP algorithm performs best when its input array is in the decreasing order [28]. Additionally, we initialize the array containing the remaining normalized capacity of every wavelength (denoted by $C_{\lambda }$). This array is given as where $C_{N_w}$ denotes the remaining normalized capacity of $N_w^{th}$ wavelength, and is defined as the difference between the maximum normalized capacity of any wavelength (denoted by $C$) and already assigned capacity. We initialize the value of $C$ as one. Furthermore, at the beginning of a WMA cycle, all wavelengths have full capacity resulting in $C_{\lambda }$ to be a unit array (i.e., $C_{\lambda } = [1, \ldots , 1]$). The rest of the steps for WMA using the BF-BP algorithm (c.f., Algorithm 1) are as follows:- • We begin by considering that the number of wavelengths currently active is one, and denote this number by $w$ (in line 1). $w$ varies from 1 to $N_w$.
- • From lines 2 to 24, we apply our version of the BF-BP algorithm to allocate the appropriate wavelength for every ONU.
- • For every ONU, we begin by initializing $m_s$, i.e., the residual space available on a wavelength and $b$, i.e., the index of the most appropriate wavelength for the $i^{th}$ ONU (see line 3). We find the value of $b$ using this BF-BP algorithm.
- • From lines 4 to 9, we find the best suitable wavelength for the $i^{th}$ ONU among the active wavelengths. In line 5, we check two conditions: first, we check whether $k^{th}$ wavelength can satisfy the $\rho _i$ requirement of $i^{th}$ ONU and second, we check whether $k^{th}$ wavelength has the minimum residual capacity after accommodating $i^{th}$ ONU. The value of $k$ varies from one to $w$ (see line 4). If such a wavelength is present, we store that wavelength in variable $b$ and update $m_s$ (see lines 6 and 7).
- • Lines 10 to 12 work if the condition in line 5 is true. This means $b$ is the most appropriate wavelength for $i^{th}$ ONU. Hence, we place $i^{th}$ ONU on $b^{th}$ wavelength and update its remaining normalized capacity (in lines 11 and 12).
- • Lines 13 to 23 work if the condition in line 5 is false, i.e., none of the active wavelengths can accommodate $i^{th}$ ONU. In line 14, we check whether $w$ is less than $N_w$ or not. This is done to limit the maximum number of wavelengths to $N_w$. If $w$ is less than $N_w$, then we increase the number of active wavelengths by one (in line 15) and place $i^{th}$ ONU on this new active wavelength (whose index is stored in $w$). We, then update the remaining normalize capacity of $w^{th}$ wavelength (see line 17).
- • Lines 18 to 21 work if the number of active wavelengths is equal to $N_w$ (i.e., the maximum number of available wavelengths), and none of the active wavelengths can accommodate $i^{th}$ ONU. In this case, we find the wavelength with the maximum remaining capacity (stored in variable $m$) and place the ONU on this wavelength (see lines 19 and 20). We then update the remaining normalized capacity of $m^{th}$ wavelength (in line 21).
Furthermore, there may be a case where any available wavelength cannot fulfil the ONUs requirements at a high network load. For such cases, a new wavelength is not a solution as all available wavelengths are active. Therefore, we cut short the requirements of such ONU and assigned it to the wavelength with the maximum capacity. Additionally, in the case of fewer ONUs, there may be a scenario where there is just one ONU on a wavelength. For such a scenario, we need to change the calculations for the GATE message scheduling time and the sleep time of the ONU as they both are dependent on the timings of the ONU that lies just before the current ONU.
3.2 UBF-SMA
The BF-BP algorithm that we employ for WMA in the case of the BF-SMA algorithm provides the most suitable wavelength for every ONU. However, it does not have any condition that restricts wavelength switching. As mentioned earlier, the unrestricted switching of wavelengths adds to the network latency. So, we modify the BF-BP algorithm (given by Algorithm 1) by introducing a condition to limit wavelength switching and name this technique as UBF-SMA. This condition is discussed below.
3.2.1 Condition to limit wavelength switching
At the OLT end, we know the current wavelength allocation of every ONU. For every ONU, if the current remaining capacity of its previous WMA cycle wavelength can fulfil the current requirements of the ONU, then we do not switch the ONU and retain its previous wavelength. This condition is given as follows
where $C_{p,i}$ is the previous WMA cycle wavelength of $i^{th}$ ONU. The first condition in Eq. (7) checks whether the available capacity on $p^{th}$ wavelength can accommodate $i^{th}$ ONU or not, while the second condition makes sure that after accommodating $i^{th}$ ONU, $p^{th}$ wavelength has the minimum residual space. We check the condition given by Eq. (7) for every ONU, and if this is true for any ONU, then we do not apply the BF-BP algorithm for that ONU.For a better understanding of WMA in the UBF-SMA algorithm’s case, we provide a flowchart of this algorithm in Fig. 4. At every $T$ interval, we first initialize $i$ (i.e., the current ONU index), and $w$. We then apply the UBF-SMA algorithm for every ONU. For easy representation, we divide the algorithm’s flowchart into two cases (c.f. Figure 4).
Fig. 4. Flowchart of the proposed UBF-SMA algorithm ($m$ is the wavelength with the maximum available capacity).
Case 1: Here, we check the condition to limit wavelength switching given by Eq. (7). If the condition is true, then it means that previously assigned wavelength of $i^{th}$ ONU can accommodate it again, and we do not move to case 2. Nevertheless, if this condition is false, we execute case 2.
Case 2: In this case, we apply the BF-BP algorithm (given by Algorithm 1) to find the most appropriate wavelength having minimum residual capacity after its allocation to $i^{th}$ ONU.
We repeat these cases over and over again until we assign wavelengths for all ONUs. To make this algorithm more clear, we explain it by using an example shown in Fig. 5. In this example, we consider the sorted normalized load array (represented as $\rho$) same as the BF-SMA example (shown in Fig. 3). Now, considering the $\lambda _p$ array in the figure, we can see that we have assigned $\lambda _4$ to the fifth ONU ($N_5$). Since, $N_5$ is the first in current allocation cycle and all wavelengths are at there full capacity, $\lambda _4$ is available and we again allocate it to $N_5$ ONU. Moving forward to the case of $\rho _4$, where $N_1$ ONU is present, we can see that we have previously allocated $\lambda _1$ to this ONU. But currently $\lambda _1$ do not have enough capacity to accommodate $\rho _4$. As $\lambda _2$ is the only wavelength that can accommodate $\rho _4$, we allocated $\lambda _2$ to $N_1$. Same case happens during the wavelength allocation for $\rho _5$ and $\rho _8$. After the completion of this WMA cycle, we register only three wavelengths changes and hence only three ONUs suffer from switching latency that is the half of the case of the BF-SMA algorithm example. Furthermore, for bandwidth allocation, we use the SMA algorithm, which is an online algorithm and communicates both the activity period (or transmission slot) and sleep period. Various methods by which we determine the size of the ONU’s transmission slot are discussed in the next subsection.
3.3 Grant sizing methods
DBWA algorithms that we propose in this paper are all OLT-based polling schemes. OLT-based polling means that only the OLT can determine the grant for an active ONU. This process is known as grant sizing. Various methods for grant sizing are already in the literature [23], [29]. In this work, we are using the following grant sizing methods:
- 1. Gated: This method is dependent on the upstream traffic only. It does not limit the maximum grant size. This means that the OLT always grants as much as the ONU asks. This method is limited only by the queue size (or buffer size) of the ONU, i.e., an ONU can never demand more than its buffer size [29].
- 2. Limited: This method is dependent on the upstream traffic only. It limits the maximum grant size to $W_{max}$, where $W_{max}$ is given as In the above equation, $T_{max}$ is the maximum cycle time in which the active ONUs are polled. The grant (or transmission slot) given to the ONU (in bits) in this scheme is calculated as [23], [29] where $Min$ represents the minimum value of the function, $B_u$ represents the upstream data bytes, and $L_u$ represents the upstream line rate.
- (3) Upstream and downstream centric (UDC): This method considers both the upstream and downstream traffic to determine the grant size. In this method, the grant (or transmission slot) given to the ONU (in bits) is decided as in [23] where $Max$ represents the maximum value of the function, $B_d$ represents the downstream data bytes, and $L_d$ represents the downstream line rate. Note that considering both the upstream and downstream data bytes for grant sizing in this scheme does not impact $N_w$ calculation. Our calculation for $N_w$ is dependent only on the upstream data even for the UDC grant sizing scheme.
3.4 Power calculations
In this subsection, we discuss the power calculations for the proposed DBWA algorithms briefly. Let us assume that $P_{ONU}$ denotes the power consumption of an ONU in the active state and $P_{OLT}$ denotes the power consumption of an OLT in the active state. The average power consumption per user $(P_A)$ in the active state is given as
Let $P_{ONU,S}$ represents the power consumption of an ONU in the sleep mode, then the average power consumption per user using the sleep mode $(P_S)$ is given as4. Results and discussion
In this section, we present the evaluation of the proposed algorithms in terms of performance parameters like delay, power efficiency, fairness, and time complexity and compare them with the state-of-the-art DBWA algorithms namely HSMA [12], and BP-SMA [15].
4.1 Performance analysis
Using OMNeT++ network simulator, we study the performances of the BF-SMA, and UBF-SMA DBWA algorithms in Super-PON with 512 ONUs, and four wavelengths each in the upstream and downstream direction. We assume the upstream and downstream line rate of 10 Gbps and 40 Gbps, respectively, a maximum ONU load of 100 Mbps, the ONU buffer of size 1 MB, the maximum ONU to OLT distance of 20 km, WMA cycle interval $(T)$ as 0.1 sec, the ONU tuning time of 1 ms, and a guard time of 1 $\mu$s. Additionally, in Table 2, we provide the active and sleep mode power consumption of an ONU and the power consumption per OLT port [28]. Furthermore, we consider the traffic generation similar to [12]. The symmetric Pareto user traffic has the Hurst parameter of 0.8 and a varying packet size (64 to 1518 bytes) in the form of Ethernet frames. For the limited and UDC grant sizing method, we consider the maximum cycle time of 2 ms. Additionally, we do not consider any re-transmission delay.
Table 2. Power consumption parameters [28]
To generate a realistic traffic scenario, we also consider an asymmetric network load generation, where $20\%$ of the active users (102 users out of 512 users) generate $80\%$ of the network load, and the remaining $80\%$ of users (410 users out of 512 users) generate $20\%$ of the network load. This scenario also helps in showing that the proposed DBWA algorithms are fair in nature. Fairness in such a scenario means that every ONU irrespective of its group faces the similar average delay indicating the fair bandwidth allocation. To calculate the fairness index $(F)$ of the proposed algorithm, we use Jain’s fairness index [29] that is given as
where $N$ denotes the number of user groups, and $D_k$ denotes the average delay of $k^{th}$ group. In our case of asymmetric load, there are two groups: one generating a high network load (i.e., 102 users group) and second generating a low network load (i.e., the rest 410 users group). Additionally, it is well known that the value of $F$ varies from $1/N$ to one, where one represents the best case scenario indicating fair resource allocation to all users.For symmetric network load, we compare the average upstream packet delay performance (shown using vertical right axis) and the packet loss rate (shown using vertical left axis and dashed line) of the proposed BF-SMA and UBF-SMA algorithms with the HSMA and BP-SMA algorithms in Fig. 6. In Fig. 6(a), we present the results for Super-PON considering the gated grant sizing scheme, in Fig. 6(b), we present the results for Super-PON with the limited grant sizing scheme, and in Fig. 6(c) the results are for the UDC grant sizing scheme. The impact of wavelength minimization and addition according to network load is visible in the form of rise and fall in the average delay graphs. In the case of the BF-SMA algorithm, for all the considered grant sizing schemes, assigning the tightest wavelength to the ONU improves the delay performance of the network significantly. Furthermore, in the UBF-SMA algorithm, the assignment of the previous cycle wavelength to the ONU (whenever possible) enhances the delay performance for all the considered grant sizing schemes. From these figures, we observe a notable improvement in the delay performance of the proposed BF-SMA and UBF-SMA algorithms compare to the state-of-the-art algorithms. In the case of low network loads, depending on the traffic burst and the transmission slot size (in case of limited and UDC scheme), the number of active wavelengths may increase to 2. Because of this, the average number of active wavelengths varies between 1.0 to 1.1. In such cases, wavelength switching happens and as the UBF-SMA algorithm has the lowest switching, it has the lowest average delay. Furthermore, the packet loss rate of the proposed BF-SMA and UBF-SMA is negligible at a low network load and is below $2.6 \%$ at high network load for all considered grant sizing schemes.
Fig. 6. Upstream delay shown using vertical right axis and packet loss rate shown using vertical left axis and the dashed line considering symmetric network load for (a) gated (b) limited (c) UDC grant sizing scheme.
In Fig. 7, we compare the percentage of power savings in the BF-SMA and UBF-SMA algorithms with the state-of-the-art algorithms. We calculate this percentage using Eq. (14). In Fig. 7(a), we show the power savings percentage considering the gated grant sizing scheme, in Fig. 7(b), the results are considering the limited grant sizing scheme in Super-PON, and in Fig. 7(c), the results are considering the UDC grant sizing scheme. From these figures, we deduce that the percentage of power savings in the proposed DBWA algorithms is notably higher than the state-of-the-art algorithms. The proposed algorithms provide the power savings of more than $76\%$ at every network load. The power efficiency of the UBF-SMA algorithm is highest. This is because switching wavelengths incurs an overhead that increases the up time of the wavelength, as a result of which, the number of wavelengths used in any other algorithm is larger than the UBF-SMA algorithm on average.
Fig. 7. Percentage of power savings considering symmetric network load for (a) gated (b) limited (c) UDC grant sizing scheme.
To compare the impact of delay on packet loss rate for the proposed algorithms and the state-of-the-art-algorithms, we present Fig. 8. Figure 8(a) provides the trade-off between the average delay and packet loss rate for the gated grant sizing scheme. In Fig. 8(b), we provide the results considering the limited grant sizing scheme, and in Fig. 8(c), the results consider the UDC grant sizing scheme. From these graphs, it is evident that as the delay increases, the packet loss rate also increases. Additionally, for the proposed UBF-SMA algorithm, the packet loss rate is lowest (below $1\%$) in the case of the gated grant sizing scheme.
Fig. 8. Upstream delay vs. packet loss rate considering symmetric network load for (a) gated (b) limited (c) UDC grant sizing scheme.
To show the trade-off between delay and fairness, we consider two different ONUs arrangement in the proposed DBWA algorithm and present the results in Fig. 9 and Fig. 10. In Fig. 9(a), we present the delay performance and fairness index (shown using the dashed line and vertical left axis) of the UBF-SMA algorithm considering asymmetric network load and the ONU load array $\rho$ sorted in the decreasing order for the gated grant sizing scheme. The average network load of these 512 users is shown on the x-axis of the graph. Additionally, we use right Y-axis only for the plot line. In order to find the saturation point of the average delay, we increase the network load range to 1.2 in this case. The indistinguishable difference between the average delay of the low loaded ONUs and the high loaded ONUs group result in a fairness index closer to one at all network loads. This indicates that the UBF-SMA algorithm provides fair resource allocation to all ONUs considering the gated grant sizing scheme and descending sorted $\rho$. Similar to the previous graphs, the maxima and minima (or rise and fall) in the graph occur due to wavelength minimization and addition. This nature of the graphs is similar to the results in [12], [30]. Furthermore, in Fig. 9(b), we show the change in the upstream delay and fairness index with the network load for the UBF-SMA algorithm, asymmetric load, gated grant sizing scheme, and $\rho$ sorted in ascending order. From the figure, we observe that the proposed DBWA algorithm, in this case, is fair for most of the network load values. However, sorting $\rho$ in ascending order results in higher delay values. Furthermore, in Fig. 9(c), we present the change in the packet loss rate with the network load for two different ONUs’ arrangement (i.e., decreasing and increasing). From this figure, we observe that the packet loss rate is below $2\%$ at every network load in the case of decreasing ONU arrangement. However, in the case of increasing ONU arrangement, the packet loss rate increases with the highest value of about $3.5 \%$. Additionally, we show the trade-off between the average upstream delay and the packet loss rate for decreasing and increasing arrangement of ONUs in Fig. 9(d). From this figure, we observe that the packet loss rate is highest when the delay is highest. The highest delay in the case of the increasing arrangement of the ONUs is around 80 msec, and the packet loss rate is also highest at this point ($3.2 \%$ approx.).
Fig. 9. For UBF-SMA gated scheme and asymmetric load (a) delay shown using vertical right axis and fairness index shown using vertical left axis and dashed line with decreasing ONUs arrangement (b) delay shown using vertical right axis and fairness index shown using vertical left axis and dashed line with increasing ONUs arrangement (c) packet loss rate vs. network load (d) delay vs. packet loss rate.
Fig. 10. For UBF-SMA limited scheme and asymmetric load (a) delay shown using vertical right axis and fairness index shown using vertical left axis and dashed line with decreasing ONUs arrangement (b) delay shown using vertical right axis and fairness index shown using vertical left axis and dashed line with increasing ONUs arrangement (c) packet loss rate vs. network load (d) delay vs. packet loss rate.
In Fig. 10(a), we observe the average delay and fairness index for the UBF-SMA algorithm considering a limited grant sizing scheme and arranging $\rho$ in descending order. The fairness index is higher than 0.95 at every network load, indicating that UBF-SMA is a fair algorithm. Additionally, in Fig. 10(b), we provide the average delay and fairness index considering the same limited scheme system with $\rho$ arranged in ascending order. Although the delay performance, in this case, is better than in Fig. 9(a), the fairness index varies with the network load making this arrangement a less fair one. Additionally, we show the variation of packet loss rate with the network load for decreasing and increasing arrangement of the ONUs in Fig. 10(c). For decreasing ONUs arrangement, the packet loss rate is below $2\%$ at every network load, while for increasing ONUs arrangement, the packet loss rate increases to $3.5\%$ at the network load of 1. Furthermore, in Fig. 10(d), we show the change in the average upstream delay with the packet loss rate for different arrangements of the ONUs. Similar to the previous figure, in this case also, the packet loss rate increases with the delay. In the case of decreasing ONU arrangement, the highest delay is around 60 msec, and the packet loss rate is the highest, around $2 \%$ for it.
4.2 Complexity analysis
The time complexity of any algorithm is of great importance as it determines its real-time implementation. For the worst-case time complexity of the proposed algorithm, we consider the pseudo-code presented in Algorithm 1. In this algorithm, we can see that the primary operations are For and If-Else loop. The For loop has the time complexity of $O(n)$ where $n$ is the number of times we execute the loop. For If-Else loop, the complexity order is the highest among both If and Else loop. Additionally, in Algorithm 1, we perform a binary search to find the best fit wavelength (line 4 to 8). The worst-case time complexity of this case is $O(log(N_w))$. Furthermore, we execute the For loop (in line 2) $N_o$ times (i.e., $n=N_o$) resulting in time complexity of $O(N_o)$. Therefore, the worst-case time complexity of the proposed algorithms is $O(N_olog(N_w))$.
5. Conclusion
In this paper, we proposed two novel power-efficient offline DBWA algorithms for Super-PON, namely BF-SMA and UBF-SMA. These proposed algorithms use the BF-BP (or UBF-BP) schemes for wavelength minimization and allocation that results in efficient wavelength utilization and in turn, improving the power efficiency and reducing the complexity. Additionally, to enhance the network’s power-efficiency, we use the SMA algorithm for bandwidth assignment that aids in assigning an appropriate sleep period to the ONUs. The simulation results show that the proposed algorithms have improved delay performance (approx. $60\%$ less for the gated scheme, approx. $45\%$ less for the limited scheme, and approx. $50\%$ less for the UDC scheme), and power efficiency (approx. $8\%$ more for the gated scheme, approx. $9\%$ more for the limited scheme, and approx. $10\%$ more for the UDC scheme) in comparison to the state-of-the-art algorithms. Furthermore, to check the fairness of the proposed algorithms, we consider a realistic user scenario and use Jain’s fairness index for its assessment. In this case of an asymmetric user scenario, the fairness index of more than 0.95 indicates that the UBF-SMA algorithm is a fair scheme when the ONUs are arranged in descending order according to their load, considering the gated and limited grant sizing schemes. Furthermore, the packet loss rate of the UBF-SMA algorithm is below $2\%$ for every considered scenario showing that it has proper channel utilization. Future work can consider introducing the non-linear buffering so that the spikes in the network delay with the addition and deletion of wavelengths can be further reduced.
Disclosures
The authors declare no conflicts of interest.
Data availability
No data were generated or analyzed in the presented research.
References
1. Cisco Visual Networking Index: Forecast and Methodology Available 2016–2021. https://www.cisco.com/c/dam/en/us/solutions/collateral/service-provider/visual-networking-index-vni/complete-white-paper-c11-481360.pdf.
2. M. SafaeiSisakht, A. Nikoukar, H. Goudarzi, I. S. Hwang, and A. T. Liem, “Lattice based EPON energy-saving scheme analysis,” Opt. Fiber Technol. 57, 102243 (2020). [CrossRef]
3. S. H. S. Newaz, M. S. Jang, F. Y. M. Alaelddin, G. M. Lee, and J. K. Choi, “Building an energy-efficient uplink and downlink delay aware TDM-PON system,” Opt. Fiber Technol. 29, 34–52 (2016). [CrossRef]
4. J. Pan and J. McElhannon, “Future edge cloud and edge computing for internet of things applications,” IEEE Internet Things J. 5(1), 439–449 (2018). [CrossRef]
5. A. F. Pakpahan and I. S. Hwang, “Enabling flexible software-defined energy-efficient orchestration in TWDM-PON,” J. Internet Technol. 21, 365–374 (2020). [CrossRef]
6. IEEE std 802.3ca-2020, “IEEE standard for Ethernet amendment 9: Physical layer specifications and management parameters for 25 Gb/s passive optical networks,” 1–267 (2020).
7. D. Nesset, “PON roadmap,” J. Opt. Commun. Netw. 9(1), A71–A76 (2017). [CrossRef]
8. C. DeSanti, L. Du, J. Guarin, J. Bone, and C. F. Lam, “Super-PON: an evolution for access networks,” J. Opt. Commun. Netw. 12(10), D66–D77 (2020). [CrossRef]
9. L. B. Du and C. F. Lam, “Super-PON: technology and standards for simplifying FTTH deployment,” in OSA Photonic Netw. and Devices, NeTu2B-1 (2020).
10. L. Zhang, J. Qi, K. Wei, W. Zhang, Y. Feng, and W. Hou, “High-priority first dynamic wavelength and bandwidth allocation algorithm in TWDM-PON,” Opt. Fiber Technol. 48, 165–172 (2019). [CrossRef]
11. K. Kondepu, L. Valcarenghi, D. P. Van, and P. Castoldi, “Trading energy savings and network performance in reconfigurable TWDM-PONs,” J. of Optical Commun. and Netw. 7(5), 470–479 (2015). [CrossRef]
12. A. Dixit, B. Lannoo, D. Colle, M. Pickavet, and P. Demeester, “Novel DBA algorithm for energy efficiency in TWDM-PONs,” 39th IET European Conf. and Exhibition on Optical Commun. (ECOC, 2013), 1–3.
13. Y. Xiong, P. Sun, C. Liu, and J. Guan, “Traffic-aware energy saving scheme with modularization supporting in TWDM-PON,” Opt. Fiber Technol. 33, 7–15 (2017). [CrossRef]
14. A. F. Pakpahan, I. S. Hwang, and A. Nikoukar, “OLT energy savings via software-defined dynamic resource provisioning in TWDM-PONs,” J. of Optical Commun. and Netw. 9(11), 1019–1029 (2017). [CrossRef]
15. S. Garg and A. Dixit, “Novel dynamic bandwidth and wavelength allocation algorithm for energy efficiency in TWDM-PON,” in 21st IEEE International Conf. on Transparent Optical Netw. (ICTON, 2019), 1–4.
16. M. Hadi, C. Bhar, and E. Agrell, “General QoS-aware scheduling procedure for passive optical networks,” J. of Optical Commun. and Netw. 12(7), 217–226 (2020). [CrossRef]
17. A. C. Yao, “New algorithms for bin packing,” J. ACM 27(2), 207–227 (1980). [CrossRef]
18. M. P. McGarry, M. Reisslein, M. Maier, and A. Keha, “Bandwidth management for WDM EPONs,” J. Opt. Netw. 5(9), 637–654 (2006). [CrossRef]
19. K. Kanonakis and I. Tomkos, “Improving the efficiency of online upstream scheduling and wavelength assignment in hybrid WDM/TDMA EPON networks,” IEEE J. Select. Areas Commun. 28(6), 838–848 (2010). [CrossRef]
20. C. Kenyon, “Best-fit bin-packing with random order,” In SODA 96, 359–364 (1996).
21. K. A. Memon, Q. Zhang, R. A. Butt, K. H. Mohammadani, M. Faheem, N. Ul Ain, F. Tian, and X. Xin, “Traffic-adaptive inter wavelength load balancing for TWDM PON,” IEEE Photonics J. 12(1), 1–8 (2020). [CrossRef]
22. Z. Li, L. Yi, and W. Hu, “Key technologies and system proposals of TWDM-PON,” Front. Optoelectron. 6(1), 46–56 (2013). [CrossRef]
23. A. Dixit, B. Lannoo, D. Colle, M. Pickavet, and P. Demeester, “Energy efficient dynamic bandwidth allocation for Ethernet passive optical networks: Overview, challenges, and solutions,” Opt. Switching and Netw. 18, 169–179 (2015). [CrossRef]
24. L. Wei, Z. Luo, R. Baldacci, and A. Lim, “A new branch-and-price-and-cut algorithm for one-dimensional bin-packing problems,” INFORMS J. on Computing 32(2), 428–443 (2020). [CrossRef]
25. K. Psychas and J. Ghaderi, “High-Throughput Bin Packing: Scheduling Jobs With Random Resource Demands in Clusters,” IEEE/ACM Trans. on Netw. 29(1), 220–233 (2021). [CrossRef]
26. Y. Fu and A. Banerjee, “Heuristic/meta-heuristic methods for restricted bin packing problem,” J. Heuristics 26(5), 637–662 (2020). [CrossRef]
27. X. Li and K. Zhang, “Single batch processing machine scheduling with two-dimensional bin packing constraints,” Int. J. of Production Economics 196, 113–121 (2018). [CrossRef]
28. S. Garg and A. Dixit, “Evaluating power saving techniques in passive optical access networks,” Photonics Netw. Commun. 4, 1–14 (2021). [CrossRef]
29. R. K. Jain, D. M. W. Chiu, and W. R. Hawe, “A quantitative measure of fairness and discrimination,” Eastern Research Laboratory, Digital Equipment Corporation, 1–38 (1984)s.
30. M. P. I. Dias, D. P. Van, L. Valcarenghi, and E. Wong, “Energy-efficient dynamic wavelength and bandwidth allocation algorithm for TWDM-PONs with tunable VCSEL ONUs,” IEEE OptoElectronics and Communication Conference and Australian Conference on Optical Fibre Technology, 1007–1009 (2014).
