Author's Accepted Manuscript

High utilization dynamic bandwidth alloca-

tion algorithm based on sorting report mes-
sages with additive-polling thresholds in
EPONs
Jiunn-Ru Lai, Wen-Ping Chen

www.elsevier.com/locate/osn

PII: S1573-4277(15)00035-1
DOI: http://dx.doi.org/10.1016/j.osn.2015.04.003
Reference: OSN353

To appear in: Optical Switching and Networking

Received date: 25 November 2014

Revised date: 26 April 2015
Accepted date: 27 April 2015

Cite this article as: Jiunn-Ru Lai, Wen-Ping Chen, High utilization dynamic
bandwidth allocation algorithm based on sorting report messages with
additive-polling thresholds in EPONs, Optical Switching and Networking, http://dx.
doi.org/10.1016/j.osn.2015.04.003

This is a PDF file of an unedited manuscript that has been accepted for
publication. As a service to our customers we are providing this early version of
the manuscript. The manuscript will undergo copyediting, typesetting, and
review of the resulting galley proof before it is published in its final citable form.
Please note that during the production process errors may be discovered which
could affect the content, and all legal disclaimers that apply to the journal
pertain.
High utilization dynamic bandwidth allocation algorithm based on
sorting report messages with additive-polling thresholds in EPONs

Jiunn-Ru Lai* and Wen-Ping Chen

Department of Electrical Engineering, National Kaohsiung University of Applied Sciences, Taiwan

#415 Chien Kung Road, Kaohsiung, Taiwan, R.O.C. 80717

E-mail: jrlai@cc.kuas.edu.tw

Phone: 886-7-3814526-5502, Fax: 886-7-3921073

ABSTRACT

High utilization is one of the design goals for MPCP-based dynamic bandwidth allocation
(DBA) algorithms in Ethernet passive optical networks (EPON). However, utilization is sacrificed
in order to meet the delay limits of the applications in most DBA design schemes. This paper
proposes a dynamic bandwidth allocation algorithm based on sorting report messages with
additive-polling thresholds (AP-Sort DBA). This has the characteristics of high utilization and low
delay during medium network loading. AP-Sort DBA is an extension of the adaptive Dynamic
Bandwidth Allocation algorithm with Sorting report messages (Sort-DBA) and promotes utilization
by reduction of unused slot remainders (USR) and distribution of excess bandwidth. For
performance evaluation in terms of average delay, average queue size, loss rate and utilization, five
DBA schemes are simulated, namely AP-Sort DBA, Interleaved Polling with Adaptive Cycle Time
(IPACT), Dynamic Bandwidth Allocation with a modified grant table generation algorithm and
Fair-Excess allocation (DBA2-FE), Sort-DBA and Double-phase Polling Algorithm (DPA).
Self-similar traffic and OC-3 packet size distribution are used for frame generation. The results
show that AP-Sort DBA can achieve up to 99% utilization, which is the highest among the tested
alternatives, with up to 60% improved delay compared to the IPACT. Technical analysis is
presented for further proof of the effectiveness of the proposed methodology.

Keywords: High utilization dynamic bandwidth allocation algorithm in Ethernet passive optical
networks; reduction of unused slot remainders
I. INTRODUCTION

The increasing demand for bandwidth among user applications such as voice, video, FTP, P2P,
and multimedia traffic in MAN (metropolitan area networks) and LAN (local access networks) is
driving ISP (Internet service providers) to provide high speed access networks. Because of
advantages in implementational complexity, bandwidth and maintenance costs, PON (passive
optical networks) have become an attractive solution for the building of high speed access networks.
Based on the PON infrastructure, various types of networking technologies such as WDM
(wavelength division multiplexing), ATM (asynchronous transmission mode) and Ethernet can be
employed for data transmission [1,2]. Among them, the combination of Ethernet and PON (called
EPON) is currently attracting the most attention because of the widely used, cost effective and
easily implemented advantages of Ethernet. In IEEE 802.3ah [3,4], EPON technology is
standardized for improving broadband service. The typical EPON network topology is the tree
structure used for point-to-multipoint (P2MP) communication. As shown in Fig. 1, the network
components consist typically of at least one optical line terminal (OLT), a group of optical network
units (ONU) and at least one passive splitter/connector. The OLT, located near the central office
(CO) of the service provider, is responsible for arbitration of line access among the ONUs and also
bridges the users behind the ONU to the backbone networks. The ONU is generally placed at the
curb [i.e. fiber-to-the-curb (FTTC) solution] or the end-user location [i.e. fiber-to-the-building
(FTTB) and fiber-to-the-home (FTTH)], providing broadband video, data and voice services for the
users behind it. The main responsibility of the ONU is the provision of network access service to
users according to their service level agreement (SLA).
From the perspective of data flow, in the downstream direction (from the OLT to the ONU),
the OLT broadcasts data to ONUs in a one-to-many fashion. The ONU discards the frames which
are not destined to it by recognizing the destination address field of the Ethernet frame. However, it
is more complicated in the up-stream direction. All the ONUs are connected with the OLT by a 1:N
passive splitter. Contention and collision prevent the ONUs from transmitting in the upstream
direction. An arbitration mechanism typically lying in the OLT is needed for shared media access
control (MAC). A dynamic bandwidth allocation scheme for the OLT is needed to arrange the
transmission start time and its corresponding duration for all the ONUs. The multipoint control
protocol (MPCP) defined in IEEE 802.3ah is designed for the assistance of OLT dynamic
bandwidth allocation operation in EPONs. There is no mandatory DBA algorithm specified in
MPCP. On the contrary, MPCP provides a framework for facilitating the implementation of various
allocation algorithms in EPON. In the MPCP, report messages are used to carry the bandwidth
requirement of the ONUs to the OLT and the multiplexing of multiple transmitters is achieved
through the grant messages. Recently, research on the enhancement of MPCP with look-ahead
operation is exploited in [5] to open up new opportunities for the design of sophisticated DBA
schemes. Detailed investigation of the impact of the report message scheduling (RMS) for 1G/10G

1
EPON and GPON can be found in [6]. The research found that the report message, which is
generally scheduled at end of an ONU upstream transmission can have the reduction in channel idle
time if it is scheduled at the beginning.
With the help of the report and grant messages in MPCP, various DBA design schemes are
proposed. Detailed survey on DBA design can be found in [7]. Among the DBA schemes, there are
proposals [8-11] which target high utilization by means of upstream idle time elimination. The
upstream idle time is defined in a similar way as [8] did. The interval spans from the moment that
the last bit of the ONU report arrives at the OLT to the point that the first bit of ONU data
transmission is scheduled to arrive at the OLT. From the perspective of a specific ONU, it is
prohibited from the upstream use during this period, which may comprises intervals of the round
trip time (RTT), the OLT DBA computation time and the ONU grant processing time. One of the
representative proposals is the adaptive Dynamic Bandwidth Allocation algorithm with Sorting
report messages (Sort-DBA) [11], which uses the sorting report messages in DBA operation.
Another is Double-phase Polling Algorithm (DPA) [10], which uses subgroups to cover the idle
time. The study on investigation of the DBA algorithm design space [12] finds that the DPA
combined with the Excess:Share grant sizing mechanism [12] and the shortest propagation delay
(SPD) methodology [13] achieves the maximum channel utilization among the studied DBA
algorithms. However, these proposals do not consider the unused slot remainder (USR) [14]
problem. As seen in Fig. 2, the waste of bandwidth comes from the gap between the maximum
granted transmission window and the border of the frames in the ONU’s buffer. The gap cannot be
used because the Ethernet frame cannot be fragmented. There are many papers [15-19] dealing with
the USR problem, One of the current directions of solution is to use MPCP’s report with queue
thresholds mechanism [15,16]. However, the design of the threshold value and calculation of the
queue report thresholds at the ONU, which involves thirteen threshold value computation updates
for each queue at the ONU during one cycle time hinders practical use of this mechanism.
In this present study, we propose a new dynamic bandwidth allocation algorithm based on
sorting report messages with additive-polling thresholds (AP-Sort DBA) for high utilization in
EPONs. We combine the Sort-DBA algorithm, a USR reduction mechanism and the excess
bandwidth allocation mechanism to achieve the high utilization design goal. This is because the
Sort-DBA can improve delay performance during medium network loads while achieving high
utilization during heavy loads. However, the Sort-DBA still suffers from the USR problem and
provides no excess bandwidth allocation mechanism. With consideration of MPCP compatibility
and acceptable increase in the ONU computation load, we use the additive-polling mechanism by
modifying the MPCP report messages with three queue thresholds, which require additional
computation of two queue thresholds to alleviate the USR impact. The main contribution of this
paper is that the proposed AP-Sort DBA can achieve very high utilization while improving delay
when the network is not heavily over-loaded, with little modification of MPCP reporting and with
acceptable additional computational loading of the ONU.
This paper is organized as follows. Chapter II reviews related work and the background of the

2
DBA schemes in EPONs. Chapter III presents the AP-Sort DBA algorithm and its illustration.
Analysis of the delay and utilization of the DBA schemes is also presented in this section. Chapter
IV uses simulation results to evaluate the performance of AP-Sort DBA and four other DBA
schemes in terms of average delay, average queue size, loss rate and utilization. Self-similar traffic
and OC-3 packet size distribution are used for packet generation. The final chapter concludes this
paper and summarizes its contributions.

II. RELATED WORK

The design goals of DBA schemes typically include low delay, low loss rate, high utilization
and QoS issues such as fairness and low jitter. From the perspective of high utilization, if one DBA
scheme has effective use of bandwidth, the scheme generally has better performance such as low
loss rate and low delay. This is the reason we are targeting high utilization. With the MPCP
framework, the dynamic bandwidth allocation for the ONUs at the OLT can be fulfilled with the
REPORT and GRANT messages. The bandwidth request of the ONU can be addressed in the
REPORT message during the OLT polling process. Next, after the specific DBA operation, the OLT
informs the ONU of the granted bandwidth size and the transmission start time in the next cycle
with the GRANT message. While the OLT arranges the transmission windows for the ONUs in one
cycle, the overhead waste including the guard time (needed between two successive ONU
transmission windows), REPORT, USRs and idle time is unavoidable. Generally, most of the
schemes which target high utilization begin with the elimination of idle time. In [12], from design
considerations of the DBA algorithm, the authors classify the DBA designs along three dimensions:
grant scheduling framework, grant sizing policy and grant scheduling policy. From the dimension of
the grant scheduling framework, considering the timing of DBA operation triggering, four design
types are listed: online, offline, ONU load status (OLS) and double phase polling. We review
representative designs of these four types for comparison with our AP-Sort DBA. A summary can
be found in Table 1. From the viewpoint of bandwidth usage, online DBA designs generally
perform better than others with regard to the idle time consumed. The term ‘online’ means that DBA
calculation is activated upon receiving the ONU’s request. The most representative online design is
the Interleaved Polling with Adaptive Cycle Time (IPACT) [20,21], which is also one of the
pioneering DBA designs for EPONs. The IPACT uses interleaved polling with an adaptive cycle
time to process the ONU grant upon receiving the ONU’s request. However, there tends to be
insufficient room for the OLT to take all the ONU requests into bandwidth allocation consideration.
To deal with excess bandwidth, a method of prediction or of accumulating excess bandwidth credits
[17] is needed. However, these mechanisms may result in a longer cycle time and thus degrade
performance. In this paper, we will use the IPACT as the baseline scheme for comparative
performance evaluation due to the IPACT’s high citation rate as well as its well known properties.
In offline designs, the DBA process is started after all the requests are received by the OLT.
Typically, the idle time problem is serious for this kind of design. In [11], the authors proposed the

3
Sort-DBA, an offline design which sorts the ONU report request messages to eliminate idle time.
Two cases are considered in the Sort-DBA. In one case, there is at least one request long enough to
cover the idle time. In the other case, the idle time is covered by the insertion process involving part
of the ONUs. With careful arrangement of the ordering of the ONU data transmission windows and
REPORT messages, the Sort-DBA achieves high utilization and improves delay performance when
the network is heavily loaded. However, there is still room for utilization improvement because the
Sort-DBA does not deal with the USR problem and with the allocation of excess bandwidth. Excess
bandwidth distribution techniques such as are effective for lowering average packet delay for DBA
designs. A critical evaluation of the techniques for online and offline long range PON (LR-PON)
DBA designs can be found in [22]. For single thread polling (STP) schemes, [8,23,24] have
intensely investigated this issue within the offline scheduling framework. On the basis of the
controlled excess (CE), our proposal also needs to consider the USR problem together while
distribution excess bandwidth. It is because the excess bandwidth given to the heavy load ONUs
may give rise to USR generation again. The achievement of better performance based on the
Sort-DBA is the motivation of this present study.
In OLS design, the activation timing of DBA operation depends on the status of the ONU load.
For an ONU with light loading, the request is processed at the moment of receipt and makes up the
early allocation (EA) period of the cycle which is used to cover the idle time. For heavily loaded
ONUs, their requests are processed in the same way as done by offline schemes. Excess bandwidth
allocation is easy to implement for these heavily loaded ONUs. Dynamic Bandwidth Allocation
with a modified grant table generation algorithm and Fair-Excess allocation (DBA2-FE) [8,24]
represents the OLS type design. However, the EA mechanism fails to work well when there is an
insufficiency of lightly loaded ONUs. In [9], a time tracer is proposed to check if the lightly loaded
ONUs joining during the EA period can cover the idle time. If not, a proper number of heavily
loaded ONUs is added during the EA period instead of participating in the offline DBA operation.
Although [9] improves the utilization of the DBA2-FE, it still cannot guarantee the elimination of
idle time and does not deal with the USR problem.
The representative fourth type is the DPA [10]. By dividing the ONUs into two subgroups, the
idle time of one subgroup is covered by the transmission windows of the other group. When the
offline DBA mechanism is run at subgroup one, the idle time caused by DBA calculation and
message round-trip delay is covered by the data transmission period of the other subgroup. In this
way, the DPA achieves high utilization. A hybrid DPA mode is also presented in [10], switching the
basic DPA mode with the interleaved polling mode to improve utilization when the ONU load is
light. One pioneering work on investigating the three design dimensions, namely grant scheduling
framework, grant sizing policy and grant scheduling policy, of DBA algorithms for EPONs is
presented in [12]. This work also proposes a novel Excess:Share mechanism, which permits all
ONUs to share excess bandwidth over the time period of one polling cycle in the DPA framework
and keeps the cycle length bounded by limiting the number of forwarding credits. The study [12]
finds that the design combination of the DPA scheduling framework with Excess:Share sizing

4
policy and SPD scheduling policy provides the best throughput-delay performance among the
studied DBA algorithms. However, they still did not deal with the USR problem and left room for
utilization improvement.
With the framework of MPCP, most of the cycle-based DBA designs pose a maximum
transmission size for the ONU’s grant in order to limit the length of the cycle time. An over-large
cycle time prolongs the network access delay of the ONU and hinders some delay-constrained or
delay-sensitive applications from use. Therefore, the OLT has a limitation in granting the ONU’s
transmission window size. However, the maximum granted window size may not fit the ONU’s
request and there is a possible gap between the size limit and the borderline of the frames in the
ONU buffer. That means there is frequently a frame crossing the granted transmission window size
line. However, no Ethernet frame can be fragmented so the frame crossing the line is excluded from
this cycle and is instead postponed to the next cycle. This phenomenon, referred to as the unused
slot remainder [14] problem, leads to waste of the granted bandwidth and an increase in the delay of
the frames. In [15, 16], the authors made use of MPCP’s threshold report mechanism to provide the
OLT with the details about the frame distribution of the queues in the ONUs. With proper
knowledge of the frame distribution condition of the queues, the OLT can make DBA calculations
with greater precision so as to alleviate the USR problem. However, this involves large table space
and computation on the OLT and ONU sides. In particular, the heavy computational power and the
large table memory space needed on the ONU is a serious obstacle to practical use. In [17], the
authors again tackled the USR problem using the queue threshold reporting mechanism. All the
ONUs are configured with the same queue thresholds. The lowest threshold is set to the minimum
packet size allowed in the network. The highest threshold is set to the maximum bytes the ONU is
allowed to transmit during any particular cycle. Intermediate thresholds are spaced with equal
distance between the lowest and highest values. But the number of queue reports is limited by the
space of the REPORT message. Also, information about the status of the buffer is not included. The
OLT may not make the right DBA decision without proper knowledge of the ONU’s need. In [18],
the authors discussed the USR problem for intra-ONU bandwidth allocation and addressed
elimination of the USR problem among the queues of one particular ONU by use of the modified
deficit counter scheme. However, they did not consider the inter-ONU USR problem. In [19], the
authors proposed an efficient scheduling algorithm based on inter-leaved polling for EPONs. With
modified GATE/REPORT messages and modified MPCP signaling flow, the authors addressed
solution of the inter-ONU USR problem. In a particular cycle, the ONU that is ready for data
transmission sends a REPORT message before its data transmission period to the OLT. The USR
bandwidth of this ONU in this round is recorded in the REPORT. Owing to the inter-leaved polling
mechanism, the OLT cannot perform the successive ONU’s DBA calculation before receiving the
REPORT from this particular ONU. However, with knowledge of the USR quantity of this
particular ONU, the OLT can arrange the transmission start time of the successive ONU perfectly,
without USR bandwidth waste. Unfortunately, this USR cancelation mechanism is effective only for
the inter-leaved polling scheme. Further, it is a challenge for the ONU to conduct the USR

5
calculation within a short time period.
Considering the limited processing power of the ONU, its compatibility with the original
MPCP messages and its control flow, to deal with the USR problem, we use the modified report
with queue thresholds mechanism for additive polling regarding the buffer status of the ONU. The
information carried in REPORT includes the current buffer size, MoreWmax and LessWmax. Three
sets of queue reports are used. The corresponding REPORT fields are shown in Fig. 3. The method
in the figure of carrying information about the current buffer size is commonly used by various
DBA schemes. The additive fields MoreWmax and LessWmax are for USR reduction while making
use of the Sort-DBA in our AP-Sort DBA. A detailed statement regarding the two values is
addressed in the following section of this paper. There is only one threshold value needed and it is
well-known to the ONUs joining the DBA process.
We also studied the work in [25-28] regarding analysis of the EPON DBA schemes. Most of
that work targets the gated service by which the ONU is granted what they request. However, the
traffic type is Poisson arrival, i.e. a traffic type which is convenient for mathematical analysis
because of its memory-less properties but which fails to reflect real Ethernet self-similar
characteristics. In order to compare AP-Sort DBA to other DBA schemes from the perspective of
intuition, we use simple analytical models for delay analysis and utilization of AP-Sort DBA
without the limits implied by the service type and traffic type.

III. PROPOSED SCHEME

In this section, we state how the additive-polling scheme is performed with use of the modified
report with queue thresholds mechanism. Queue status report sets defined in MPCP are used to
report the frame distribution details of a specific queue in an ONU’s buffer. Instead of using
multiple threshold values for a frame distribution report, the ONU reports three values to the OLT
for DBA operation. The three values include Lreq, LessWmax and MoreWmax. Lreq is the size of the
occupied buffer space and is typically used in various DBA schemes. LessWmax is the accumulated
frame size counting from the head of the buffer to the jth frame with which the accumulated value is
closest to Lmin [11] but still less than Lmin. MoreWmax is the sum of LessWmax and the frame size of
the (j+1)th frame. The number_of_queue_sets field in the MPCP REPORT message is set to 3 to
indicate that there are 3 sets of queue reports. Compared to the typical report usage, we use an
additional 6 bytes of the report to carry the information for additive-polling. To achieve the goal of
high utilization without the cost of increased delay, we extend the Sort-DBA with additive polling
and excess bandwidth distribution. The pseudo code of our proposal, AP-Sort DBA, is shown in Fig.
4. Additive-Polling-With-Sort-DBA() checks if the biggest ONU request, ReqL[ SL0 ], is larger
enough to cover the idle time. If true, the first part (Fig.4, line 7 to line 43) of the pseudo code is
able to eliminate the idle time completely. The first step is to calculate the excess bandwidth which
is the sum of the un-used bandwidth from the lightly loaded ONUs and the un-used slot remainders
from the heavily loaded ONUs. Next, we distribute the excess bandwidth by satisfying the heavily

6
loaded ONUs in a round robin style. If the check result is false, the insertion process of the
Sort-DBA is therefore needed to eliminate the idle time. Since all the ONUs are lightly loaded, all
the ONU requests can be satisfied. Accordingly, there is no un-used slot remainder problem.

A. Additive Polling Sort-DBA (AP Sort-DBA)

In Fig. 4, after the additive-polling report:{R} is received at the OLT, the OLT has each ONU_i
request information including the buffer status (Lreq_i), the just-below-Lmin value of the accumulated
size of frames in buffer (LessWmaxi) and the just-above-Lmin value of the accumulated size of the
frames in buffer (MoreWmaxi). There are two additional input variables needed for the
Additive-Polling-With-Sort-DBA() function. The first variable is t_Line-N/A, which records the time
before which the upstream link is not available, i.e. the upstream line is available only after t_Line-N/A.
The second variable is ONU_token, which records the ONU with the highest priority for excess
bandwidth allocation. We use the simple round robin method to circulate the priority token. The
operation starts by sorting the requests of all the ONUs in descending order. For each element SLi of
the sorted list, SL includes two fields: the ONU number (ONUNum[SLi]) and its related request size
(ReqL[SLi]). Now, judging from ReqL[SL0], we can tell if there is at least one request large enough
to cover the idle time. If ReqL[SL0] is more than Lmin, ONUNum[SL0] is supposed to be arranged as
the last ONU in this cycle to cover the idle time. Next, the OLT calculates the excess bandwidth
which is the difference between LessWmaxi and Lmin. Starting from the ONU with highest priority,
the OLT distributes the excess bandwidth to satisfy the heavily loaded ONUs one by one in order
until exhausting the excess bandwidth. After the distribution process, the satisfied heavily loaded
ONUs will be granted the amount of bandwidth they request in the report messages. However, there
may be no satisfied heavily loaded ONUs due to limited excess bandwidth. The token of highest
priority is updated after this distribution. The ONUs which do not get extra distributed bandwidth
will be granted bandwidth according to each individual LessWmax. The final step is to arrange the
order of ONU transmission. Beginning with ONUNum[SL1], Arrange-Leading-Norm-ONU-Tx()
arranges the ONU’s associated start transmission time and grant length and ends at
ONUNum[SLN-1]. For normal ONUs, reporting is arranged after data transmission.
Arrange-Longest-ONU-Tx() arranges reporting before data transmission for ONUNum[SL0] and its
associated grant length and start time.
If ReqL[SL0] is less than Lmin, the Sort-DBA-Light-Load() shown in Fig. 5 is called to handle
the idle time problem. Note that under this condition, there is no USR problem because all the
requests are granted according to their proposed need. In addition to ONUNum[SL0], the insertion
process begins with processing ONUNum[SL1] and ends with either of the two conditions: one is
that Lins is less than the guard time and the other is that all the ONUs have joined the insertion
process. The transmission sequence is headed by normal ONUs, then followed by the split reports
of the ONUs joining the insertion process, next the longest ONU and finally with the split data
transmission of the chosen ONUs in the insertion process. Note that there is the possibility that the

7
cycle begins with split reports rather than a normal ONU transmission if all the ONUs join the
insertion process.

B. Illustrative Examples

We will illustrate how AP Sort-DBA operates with two examples. First, consider the case in
which there is no single request large enough to cover the idle time. Second, consider the case with
at least one large request. In the left part of Fig. 6, the i-th round of the proposal operation is shown.
According to the ONU reports from the previous cycle, all the ONU requests are now sorted in a
descending order: Req5, ReqN-1, ReqN, …, Req1. None of these cases is larger than Lmin. So,
Sort-DBA-Light-Load() is invoked to eliminate the idle time. ONU_5 is selected as the first one for
the insertion process while the next one is ONU_N-1. In this case, the sum of the request of the two
ONUs is large enough to cover the idle time. Thus, the insertion process ends. The transmission
order of the ONUs in the i-th cycle round is arranged from ONU_N to ONU_1 for the ONUs not
joining the insertion process. Following the transmission window of ONU_1, separate reports of
those ONUs participating in the insertion process are arranged. Note that the report of the largest
ONU request, in the present case ONU_5, is arranged at last place. Next to the separate reports, the
data transmission window of the largest request is arranged at first place to save the guard time
space. The other data transmission windows of the ONUs joining the insertion process are arranged
in order according to their request size. In the right part of the figure, the second example showing
the arrangement of the (i+1)-th cycle is demonstrated. During the i-th round, the OLT has gathered
all the reports from the ONUs before the data transmission window of ONU_5 begins. In this
scenario, all the requests except the one of ONU_N-1 are larger than Lmin. The sorted requests are
listed as {ReqN, Req3, Req5, …, ReqN-1} in a descending order. Now, ONU_N is the one that takes
care of the idle time and is arranged at the end of the cycle. The report is transmitted before data
transmission for ONU_N to eliminate the idle time. The ONU transmission order is decided
according to their request size. As for the granted window size, ONUs except ONU_N are given
according to the LessWmax value in the individual report. After the AP Sort-DBA operation,
ONU_N is given the amount of the MoreWmax value in its report. In this case, the excess
bandwidth (orange color in Fig. 6), consisting of the USRs and the surplus bandwidth shares, is all
assigned to the ONU_3 that has the highest priority in this round. In this way, for the case in which
there is at least one request large enough, the idle time is eliminated and the excess bandwidth
including the USRs is distributed. This is why AP Sort-DBA achieves high utilization.
Another example is now provided to demonstrate how the excess bandwidth is distributed. In
Fig. 7, the polling table content of the (i-1)-th and i-th cycles is shown. Here is the sorted result of
the requests from all the ONUs. The fields of each entry in the table include the buffer status (Lreq),
ONU identification number ( I.D.), threshold value below Lmin (LessWmax), threshold value above
Lmin (MoreWmax) and the grant transmission window size (Grant). The requests from the ONUs in
the (i-1)-th are listed in Fig. 7-(a). In this round, there is no single request large enough to cover the

8
idle time. However, with the help of ONU_5 and ONU_15, idle time is eliminated by the insertion
process. So, the arrangement of the ONU upstream transmission for the i-th cycle is decided. It is
also shown in Fig. 6. Next, after receiving the report from ONU_5 in the i-th cycle, the polling table
is updated as shown in Fig. 7-(b). In this round, the sequence of the ordered request is {16, 3, 5, …,
15}. MoreWmax is also reported for the ONU request exceeding Lmin. For the round, the idle time
can be eliminated by arranging ONU_16 so that it reports ahead of data transmission at the last
position of this round. Total excess bandwidth comes from the surplus bandwidth share of ONU_15
and the USRs from the other ONUs. The excess bandwidth, i.e. 5.831 Kbytes, is first distributed to
ONU_3 which has the highest priority in this round. However, the request is too large to be met by
the excess bandwidth and the granted bandwidth of ONU_3 is only 30.174 Kbytes. The other ONUs
are granted their LessWmax value. ONU_3 is served in this round and is assigned the lowest priority
for excess bandwidth distribution in the next round. ONU_4 will have the highest priority in the
(i+1)-th round. The transmission arrangement of the i-th cycle is shown in Fig. 6.

C. Analytical Utilization and Delay Analysis

The present section provides analysis of the average delay performance and the utilization.
Further, we give quantitative explanation as to why the average delay behavior of the Sort-DBA is
superior to that of IPACT-LS under medium network loading conditions. In addition, it will be seen
that the proposed AP Sort-DBA scheme achieves more delay reduction than the Sort-DBA for the
reduction of USRs and the distribution of excess bandwidth. From the aspects of idle time and
overhead incurred in the different DBA schemes, we derive the utilization which is defined as the
ratio of data transmission time over the cycle time. Table 2 lists the notational usage of the system
parameters.

C-1. Delay Analysis for the Heavy Load Condition

When the ONU is heavily loaded, the delay of frames in the ONU’s buffer depends on two
main factors. One is the buffer size, which also affects the loss probability. The other is the effective
transmission window size of the ONU, which varies with different DBA schemes. We can imagine
that one specific frame arrives at an ONU and finds the buffer almost full. Intuitively, the frame has
to wait several rounds of cycles for these preceding frames to be sent out. Now, in E.Q. (1), we have
the general form of delay under heavy load circumstances. The cycle time of the individual schemes
under heavy network loading relates itself to the maximum transmission window size, the guard
time and the idle time which is dependent on the specific DBA scheme under consideration. They
are expressed in E.Q. (2). and E.Q. (3).

protocol
DHLD = ªQ / W Max
protocol
º× Tcycle
protocol , HLD
(1)

9
 protocol , HLD protocol
Tcycle = N × W Max + m × TG + l × Tidle (2)

Tidle = TDBA + RTT + TONU

(3)

The related parameters are set as follows: N = 16, RTT = 200 us, TG = 1 us, Q = 10 Mbytes and
HLD
TDBA , TONU is neglected. In the IPACT, with (m,l) = (16,0) and Tcycle = 2 ms in E.Q. (2), we can get

IPACT − LS IPACT −LS

W Max = 15 .5 Kbytes [21] and then DHLD = 1.2903 seconds from E.Q. (1). This is the

worst case of packet delay. In the DBA2-FE, with (m,l) = (16,1) and W DBA 2 − FE = 15 .5 Kbytes [8],
Max

DBA 2 − FE Sort − DBA

we get D HLD = 1.4194 seconds. In the Sort-DBA with (m,l) = (16,0) and WMax = 24.875
Sort −DBA
Kbytes [11], we get DHLD = 1.2897 seconds from E.Q. (1) and (2). It is not surprising that the
average delay value under heavy network loading depends strongly on the buffer size and slightly
on the individual DBA scheme. Although large buffer size results in increasing delay under heavy
loading, it also accommodates the variation of incoming traffic and prevents frame loss.

C-2. Delay Analysis for Medium Load Conditions

In each cycle, if the size of the frames in the buffer lies under the maximum transmission
window size of the individual DBA scheme, all the frames in the buffer should be transmitted in this
cycle. However, as the traffic increases, some of the frames in the ONU’s buffer have to wait more
than one round to be delivered. We approximate the delay value of the different DBA schemes for
the situation that the load is increasing but not heavily loaded.
First, let us consider the light load conditions where most of the frames in the ONU’s buffer
are delivered in one cycle. The mean frame delay can be approximated as the cycle time of the
specific scheme. The delay of the IPACT-LS under medium network loading is approximated in
E.Q. (4). For the DBA2-FE scheme with the early allocation mechanism, the delay value is close to
that of the IPACT-LS.
IPACT − LS i
min[W Max , Brequest ]
IPACT − LS
DMLD IPACT − LS , MLD
≈ Tcycle = ¦{ } + N × TG (4)
i∈N 8 × RU

Next, we derive the delay for the Sort-DBA based schemes represented by E.Q. (5). In the first
part, the upper limit of the maximum transmission window size of the Sort-DBA is 24.875 Kbytes,
which is bigger than the 15.5 Kbytes of the IPACT-LS. This results in an increase of the cycle time.
In the second part, the Sort-DBA makes use of the insertion process to eliminate the idle time at the
cost of more guard time gaps. This also gives rise to an increase of the cycle time. This is why the

10
delay of the Sort-DBA is worse than that of the IPACT-LS when the network load is light.
i
min[ Lmin , Brequest ]
SORT − DBA
DMLD Sort − DBA , MLD
≈ Tcycle = ¦{ } + α × N × TG (5)
i∈N 8 × RU

After examining the delay of the pre-mentioned schemes for the light load and heavy load
cases, there seems no significant difference among them. Why, then, do the Sort-DBA based
schemes outperform the other DBA schemes for the medium load condition? We found that the
answer lies in the variance of the traffic load among the ONUs during a certain period of time when
the average load of the ONUs is medium. From the perspective of the frames, the medium load
condition we mention here is the circumstance that the frames in the ONU’s buffer can be delivered
within no more than two cycles. This is valid for most of the frames in a medium-loaded ONU’s
buffer. We analyze the average delay of these frames meeting the description of the medium load
condition to approximate the delay performance of the medium-loaded ONU.
Consider that the average value of the requests from all the ONUs is close to the maximum
IPACT − LS
transmission windows size of the IPACT-LS, W Max
(15.5 Kbytes). Some requests of the ONUs

are above 15.5 Kbytes and some are under. It depends on how non-homogeneous the load
distribution is. With the IPACT-LS, an ONU that requests more than 15.5 Kbytes must have some
frames postponed to the next cycle. The amount is the difference between the request and 15.5
Kbytes. If the heterogeneous load distribution becomes worse, more frames are postponed and this
situation results in an increase of the total average delay. Under the same load distribution condition
in the Sort-DBA, an ONU requesting more than 15.5 Kbytes but less than Lmin (24.875 Kbytes) still
can deliver all the frames in its buffer in one cycle. The frames postponed in the IPACT-LS are now
free from waiting. Although the cycle time of the Sort-DBA is larger than that of the IPACT-LS, the
relief of frames waiting for one more cycle increasingly contributes to the delay improvement of the
Sort-DBA over the IPACT-LS. However, as the network load becomes heavy, almost all requests
are above Lmin and the difference between the Sort-DBA and the IPACT-LS becomes less. The
situation comes back to the C-1 section.

C-3. Utilization Analysis for the Heavy Load Condition

We define utilization as the ratio of the total time used for data transmission to the cycle time
in each individual DBA scheme. Utilization of the upstream link can barely reach 1 due to protocol
overhead and waste. From this viewpoint, we derive the general utilization equation when the
network is heavily loaded. Since the upstream link data rate is fixed, the time span given to the
ONU is equivalent to the bandwidth assigned to it. Starting from the aspect of the maximum
transmission window size of individual DBA scheme, we consider that one cycle consists of the
bandwidth part assigned to the ONUs, the guard time gaps and the idle time waste if it exists. For
the heavy load case, the bandwidth granted to the ONU is mostly equal to the maximum

11
transmission window size of the individual DBA scheme. In addition, the granted bandwidth is
shared by the data transmission, the report message and the unused slot remainder. Only the data
transmission part counts for utilization usage. Therefore, we have the general utilization equation as
E.Q. (6)

protocol TTxData ¦ (B
i∈N
protocol,i
grant − H report − k × HUSR )
U ≡ = (6)
( N × TG + l × Tidle ) × RU / 8 + ¦ Bgrant
HLD protocol, HLD protocol,i
Tcycle
i∈N

The common parameters for all DBA schemes are set as: N = 16, RTT = 200 us, TG = 1us,
Hreport = 64 bytes, RU = 1 Gbps, with the OLT and ONU processing time being neglected. From [15],
HUSR = 506.52 bytes. In the IPACT-LS, USR exists and there is no idle time. We have (k,l) = (1,0)

and W IPACT − LS = 15 .5 Kbytes. After substituting the parameters in E.Q. (6) and calculating, we have
Max

IPACT −LS
U HLD = 95.549 %. In a fashion similar to that of the DBA2-FE, we have (k,l) = (1,1) ,
DBA 2 − FE DBA 2 −FE
W Max = 15 .5 Kbytes and U HLD = 87.133 %. In the Sort-DBA, we have (k,l) = (1,0) and

Sort − DBA Sort − DBA

WMax = 24.875 Kbytes, thus yielding U HLD = 97.218 %. Finally, in AP-Sort-DBA where

Sort − DBA
the USR number is reduced, we have (k,l) = (1/16,0) and WMax = 24 .875 Kbytes for it is based
AP − Sort − DBA
on the Sort-DBA, ultimately producing U HLD = 99.117 %, which is the highest among all the
schemes.

IV. PERFORMANCE EVALUATION

Simulation results are used to evaluate the performance of our proposed scheme, AP-Sort DBA.
For more complete comparison, we also simulate four other schemes, namely IPACT-LS (limited
service) [21] which is the representative of the on-line DBA schemes, the DBA2-FE [8,24] which
stands for the off-line DBA schemes, the Sort-DBA [11] and the DPA [10], both of which achieve
high utilization. The performance of the five compared schemes is evaluated in terms of the average
delay, average queue size, loss ratio, utilization and average USR slots per cycle. Simulation setup
parameters are listed in Table 3. The simulation results verify that AP-Sort DBA achieves higher
utilization than the other schemes when the offered load is higher than 0.6, as well as providing
delay improvement when the load ranges from 0.42 to 0.66. The simulation results can also be used
to validate the result of the analytical analysis in section 3-C.

12
A. Simulation Models and Parameters

To study the performance of the four DBA schemes based on MPCP, we developed an
event-driven simulator using C++. The network topology considered here is a star network topology
consisting of an OLT and 16 ONUs. Let RU be the data rate of the upstream link between the OLT
and ONUs with a typical value of 1 Gbps. Let RD be the data rate of the access link between the
ONU and user networks with a typical value of 100 Mbps. The distance between the OLT and the
ONUs is 20 km. We assume stable RTT values, i.e. 200 us under the condition that the light speed
in fiber is 2x105 km/s. The guard time TG between two consecutive transmission windows is 1 us.
Every ONU has a finite memory buffer of Q = 10 Mbytes. The buffer management policy is FIFO
with blocking of arriving packets if the buffer is full. The offered load ranges from 0 to 1 and is
defined as the ratio of each ONU generating traffic load over RD. Therefore, in this simulation,
when the offered load equals 0.6, the aggregate traffic load on the upstream link is 960 Mbps. We
neglect the DBA processing time at the OLT and grant processing time at an ONU. The maximum
transmission window size, WMax, of an ONU is protocol specific. For the IPACT-LS, DBA2-FE and
DPA schemes, under the constraint of a maximum polling cycle time of 2 ms, WMax is 15.5 Kbytes.
As for the Sort-DBA and AP-Sort-DBA, WMax is set to 24.875 Kbytes.
To get an accurate performance evaluation of the compared schemes, we use the traffic trace
generation tool [29] which has the properties of self similarity and long-range dependence. The
traffic trace of each ONU is the aggregation of 256 sub-streams, each sub-stream consisting of
alternating ON-OFF periods. The ON period length is determined according to the Pareto
distribution with a shape parameter of 1.4. Under moderate network loading, the measured
Hurst parameter H is approximately 0.8. The Hurst parameter H also equals (3- )/2. We use the
traces observed in an MCI backbone with OC-3 links [30] to simulate the packet size distribution of
the generated traffic at the ONU. Different from a uniform distribution with packet size ranging
from 64 bytes to 1518 bytes, the packet size traces of the OC-3 links show that the cumulative
probability function of packet size distribution is dominated by several sub-periods that are not
uniformly distributed.

B. Simulation Results and Analysis

Fig. 8-a shows the average delay of the five schemes with offered load varying from 0.06 to
0.96. It can be seen that the average delay when the load is more than 0.66 goes flat and is
approximately 1.1 to 1.3 seconds, corresponding with the analytical analysis in III-C-1. To
emphasize the relative performance differences, we redraw the normalized average delay of the five
schemes with the IPACT-LS as the normalization base in Fig. 8-b. At first, let us examine how the
schemes behave when the load is light to medium. We can see that the Sort-DBA and AP-sort DBA
have at worst 1.2 times of the delay of the IPACT-LS when the load is 0.36. This is because of the

13
guard time overhead, which can be 15 us at the worst case. The overhead has a significant impact
on the link bandwidth when the offered load is light. However, the largest value of delay of the
Sort-DBA and AP-sort DBA is 0.6 ms, which is far below the 2 ms which is typically the limit of
voice traffic delay. We can say that the impact of inferior performance in AP-Sort DBA when the
load is light is small and essentially negligible. As for the DPA, it performs worst among all
schemes under light load conditions. The reason lies in that its two split groups bring out two idle
time intervals. Though the two partition subgroups are trying to cover the idle time for each other,
the aggregated load of each subgroup is not long enough to mend the idle time period and results in
higher delay. As the load grows, the delay performance of the DPA becomes close to that of the
IPACT-LS. Then, it is worth noticing that when the offered load is 0.54, AP-Sort DBA achieves up
to 60% normalized delay reduction in contrast with the large normalized delay increase in the
DBA2-FE. The main reason for the superior improvement of AP-Sort DBA lies in the enlarged
maximum transmission window size and the heterogeneous ONU load distribution, as already
stated in section III-C-2. With regard to the DBA2-FE, the ONU load distribution at this point
disables the early allocation mechanism which is responsible for idle time elimination.
Consequently, the waste of idle time results in the increased delay.
The average queue size (in bytes) of the five schemes with respect to the varying offered load
is shown in Fig. 9-a, using Pareto traffic and in Fig. 9-c, using Poisson traffic. Fig 9-b shows the
loss ratio of the five schemes with the load varying from 0.42 to 0.96. The queue size limit is equal
to the size of the buffer (10 Mbytes). In Fig. 9-a, when the ONU offered load is lower than 0.36, the
values of the schemes are close because most of the ONU requests for the compared schemes can
be satisfied and few frames in a cycle round are buffered. As the load grows higher than 0.42, the
DBA2-FE scheme needs more room for frame buffering than the others while our proposal occupies
the least buffer size. When the offered load is 0.54, value of the average buffer in the DBA2-FE
scheme is 5.4 Mbytes and the frame loss starts to occur. As for the other four schemes, the values
are all below 1 Mbytes, one tenth of the buffer limit and there is no frame loss. When the offered
load is increased to 0.6, it can be seen that AP-Sort DBA occupies the least buffer size, which
means efficient frame transmission. Consequently, it has the smallest loss ratio in Fig. 9-b. It can be
seen that the DBA2-FE loss ratio occurs earlier than other schemes due to its idle time waste. It can
also be seen that when the offered load grows over 0.66, then the upstream link is over-loaded. At
this point, the linearly-added load (over 0.66) cannot be delivered and is dropped, so the loss ratio
of all the schemes increases in proportion to the traffic overload. The steady extra loss of the
DBA2-FE is the result of the upstream bandwidth waste caused by the idle time, which remains the
same during the simulation. It is worth pointing out that the bursty nature of traffic with long-range
dependence increases the average queue size as compared to the Poisson traffic (shown in Fig. 9-c)
when the offered load is light. More buffer room is needed to prevent the frame loss for the
long-range dependent traffic.
In Fig. 10-a, we show the simulation results of the average USR number per cycle for all the
schemes while the load varies from 0.42 to 0.96. When the load is between 0.42 and 0.6, few ONU

14
requests exceed the Wmax of the compared schemes and the USR number for all schemes is small.
Owing to the additive polling and surplus bandwidth distribution mechanisms, the USR number of
our proposal is smaller than one tenth of other schemes. We find that the USR number of the
schemes exclusive of AP-Sort DBA is 16 when the load exceeds 0.6. In [18], the authors claim that
the average size of the unused slot remainder is about 506.52 bytes if the packet size is uniformly
distributed between 64 bytes and 1500 bytes. Thus, the waste of bandwidth in each cycle is up to 8
Kbytes, which is nearly half of the bandwidth granted to one ONU. In AP-Sort DBA, the USR
number is reduced to one rather than 16. The one USR is due to that the remaining surplus
bandwidth may not fit the buffer frame border of the last chosen ONU. This reduction of waste
increases the utilization of the link and provides further improvement over the Sort-DBA. Waste of
a single USR is acceptable because we use a simple modified report which involves no complicated
computation. We can see the utilization of the five schemes with respect to loads ranging from 0.42
to 0.96 in Fig. 10-b, with the term utilization referring to the portion of one cycle time being used
for ONU data transmission. The report messages and guard time intervals are considered overhead
of the protocol. Depending on the related DBA scheme, there may be idle time waste in the cycle
time which cannot be used for data transmission. It is not surprising that AP-Sort DBA achieves
99% utilization, which is highest among all the schemes. In contrast, the DBA2-FE achieves only
87% utilization, which is the lowest among the competing schemes and corresponds to the value
derived in III-C-3. The utilization of the DPA is close to that of the IPACT-LS, achieving 96% and
matching the value we derived in III-C-3. Note that the 12% difference in utilization implies 120
Mbps difference of the upstream bandwidth. Another thing worth noting is that AP-Sort DBA
outperforms the Sort-DBA by less than 2%, a difference that is supposed to be greater in the III-C-3
analysis. The reason lies in the packet size distribution used in the simulation of OC-3 traffic, with a
mean packet size of 377.8 bytes rather than 506.52 bytes.
The average vacant time per cycle and cycle time are shown in Fig.11-a and Fig. 11.b
respectively. From the perspective of one specific ONU, the idle time is an unavailable period for its
upstream use. If the period cannot be occupied fully by other ONUs, the vacant part of the period
will leaves the upstream line idle. The vacant time per cycle here is calculated as the sum of the
vacant parts of all ONUs in one cycle run. When the load is below 0.18, our proposal leaves more
vacant time because of the extra guard time overhead caused by the insertion process. As the load
increases, the possibility that there is at least one ONU request large enough increases
correspondingly. Accordingly, the vacant time in the AP-Sort DBA decreases. As the load is higher
than 0.6, the idle time of the specific ONU is completely compensated and eliminated except for the
DBA2-FE scheme, which fails in activating its early allocation mechanism. The DPA scheme has a
longer vacant time because the number of ONUs in each subgroup is only half and the idle time in
each subgroup has less chance to be compensated. The problem caused by the two idle time periods
also results in longer cycle time for the DPA scheme in Fig. 11.b. For the other four schemes, the
average cycle time increases very slowly from 0.21 ms to 0.25 ms when the load varies from 0.06 to
0.42. During this load interval, the cycle time can be roughly approximated by the sum of the idle

15
time (more than RTT) and the grant length of the ONU who reports the largest bandwidth request.
As the offered load increases from 0.42 to 0.6, the cycle time grows at a faster speed to the
maximum cycle time as compared to the previous interval. For this load interval, the cycle time now
is dominated by total ONUs’ aggregated traffic. Consider that the time overhead consumed by the
guard time and report messages in a cycle round is constant. It can be observed that the increasing
aggregated traffic drives the stretching of the cycle time to obtain more percentages of the cycle
time for traffic transmission. As the load increases higher than 0.6, the lines go flat at the
pre-determined maximum cycle time: 2 ms, 2.2 ms and 3.2 ms respectively. The maximum cycle
time is determined by the Wmax specified in different schemes.

V. CONCLUSION

In this paper, we have proposed a dynamic bandwidth allocation algorithm based on sorting
report messages with additive-polling thresholds (AP-Sort DBA) for EPONs. The merits of our
work include high bandwidth utilization, low average packet delay, low packet loss rate, low unused
slot remainder and MPCP compatibility. Extending from the work of the Sort-DBA which helps
solve the idle time problem, we make use of the modified report with queue thresholds mechanism
defined in MPCP for additive polling. With additive polling information, we can reduce the
bandwidth waste caused by the unused slot remainder, which is usually 2% ~ 3% of the bandwidth.
As for the excess bandwidth including unused slot remainders, we make use of the round robin
distribution method because of its easy implementation and light computational load. Simulation
results were used to evaluate the performance of our proposal in terms of average queue delay,
average queue size, loss rate and utilization. The results show that AP-Sort DBA can achieve up to
99% line utilization, highest among all the compared schemes. As compared to the DBA2-FE
scheme, AP-Sort DBA increases utilization by 12%, i.e. 120 Mbps improvement. Regarding the
average queue delay, with the load ranging from 0.24 to 0.36, AP-Sort DBA has a higher delay
value ranging from 0.4 ms to 0.5 ms, i.e. about 25% higher compared to the IPACT-LS scheme.
However, a delay value of 0.5 ms is still acceptable for most application needs. It is worth noting
that AP-Sort DBA can achieve about 60% reduction of delay compared to the IPACT-LS scheme
under medium network loading. AP-Sort DBA effectively increases line utilization without
sacrificing delay performance. This is the main difference relative to previous work.
Future direction of our research will consider: providing quality-of-service (QoS) or
class-of-service (CoS) in AP-Sort DBA with addition design goals such as fairness and low jitter;
applying AP-Sort DBA to long-range EPONs (LR-PONs) [22,31-33] and to high utilization DBA
design in GPON [34]; evaluating the performance impact of AP-Sort DBA with asymmetric
network loads.

16
REFERENCES

[1] F. Effenberger, D. Cleary, O. Haran, G. Kramer, R. Li, M. Orin, T. Pfeiffer, An introduction to PON
Technologies, IEEE Communications Magazine 45 (3) (2007) 17–25.
[2] K. Kim, On the evolution of PON-based FTTH solutions, Information Sciences, 149 (1 & 3) (2003) 21–30.
[3] IEEE 802.3ah Ethernet in the First Mile Task Force [Online] Available: http://www.ieee802.org/3/efm
[Accessed 28 February 2012]
[4] D. Law, D. Dove, J. D'Ambrosia, M. Hajduczenia, M. Laubach, S. Carlson, Evolution of Ethernet standards
in the IEEE 802.3 working group, IEEE Communications Magazine 51 (8) (2013) 88–96.
[5] X. Liu, G. Rouskas, F. He, H. Xiong, Multipoint control protocol with look-ahead for wavelength division
multiplexed Ethernet passive optical network, IEEE/OSA Journal of Optical Communications and
Networking 6 (2) (2014) 104–113.
[6] A. Mercian, M. McGarry, M. Reisslein, Impact of report message scheduling (RMS) in 1G/10G EPON and
GPON, Optical Switching and Networking 12 (2014) 1–13.
[7] M. McGarry, M. Reisslein, M. Maier, Ethernet passive optical network architectures and dynamic
bandwidth allocation algorithms, IEEE Communications Surveys & Tutorials 10 (3) (2008) 46–60.
[8] C. M. Assi, Y. Ye, S. Dixit, M. A. Ali, Dynamic bandwidth allocation for quality-of-service over Ethernet
PONs, IEEE Journal on Selected Areas in Communications 21 (9) (2003) 1467–1477.
[9] J. Zheng, Efficient bandwidth allocation algorithm for Ethernet passive optical networks, IEE Proceedings
of Communications 153 (3) (2006) 464–468.
[10] S. Choi, S. Lee, T.-J. Lee, M. Chung, H. Choo, Double-phase polling algorithm based on partitioned ONU
subgroups for high utilization in EPONs, IEEE/OSA Journal of Optical Communications and Networking 1
(5) (2009) 484–497.
[11] W. Chen, W. Wang, W. Huang, Adaptive dynamic bandwidth allocation algorithm with sorting report
messages for Ethernet passive optical network, IET Communications 4 (18) (2010) 2230–2239.
[12] M. McGarry, M. Reisslein, Investigation of the DBA algorithm design space for EPONs, IEEE/OSA
Journal of Lightwave Technology 30 (14) (2012) 2271–2280.
[13] M. McGarry, M. Reisslein, F. Aurzada, M. Scheutzow, Shortest propagation delay (SPD) first scheduling
for EPONs with heterogeneous propagation delays, IEEE Journal on Selected Areas in Communications 28
(6) (2010) 849–862.
[14] G. Kramer, B. Mukherjee, S. Dixit, Y. Ye, R. Hirth, Supporting differentiated classes of service in Ethernet
passive optical networks, Journal of Optical Networking 1 (8 & 9) (2002) 280–298.
[15] D. Nikolova, B. V. Houdt, C. Blondia, Dynamic bandwidth allocation algorithms in EPON: a simulation
study, in: Proceeding of Optical Networking and Communications (OptiComm), 2003.
[16] D. Nikolova, B. V. Houdt, C. Blondia, Dynamic bandwidth allocation algorithms for Ethernet passive
optical networks with threshold reporting, Telecommunication Systems 28 (1) (2005) 31–52.
[17] H. Naser, H. T. Mouftah, A joint-ONU interval-based dynamic scheduling algorithm for Ethernet Passive
Optical Networks, IEEE/ACM Transactions on Networking 14 (4) (2006) 889–899.
[18] G. Kramer, A. Banerjee, N. K. Singhai, B. Mukherjee, S. Dixit, Y. Ye, Fair queueing with service
envelopes (FQSE): a cousin-fair hierarchical scheduler for subscriber access networks, IEEE Journal on
Selected Areas in Communications 22 (8) (2004) 1497–1513.
[19] B. Chen, J. Chen, S. He, Efficient and fine scheduling algorithm for bandwidth allocation in Ethernet
passive optical Networks, IEEE Journal of Selected Topics in Quantum Electronics 12 (4) (2006) 653–660.
[20] G. Kramer, B. Mukherjee, G. Pesavento, Ethernet PON (ePON): Design and analysis of an optical access
network, Photonic Network Communications 3 (3) (2001) 307–319.
[21] G. Kramer, B. Mukherjee, G. Pesavento, IPACT: A dynamic protocol for an Ethernet PON (EPON), IEEE
Communications Magazine 40 (2) (2002) 74–80.
[22] A. Mercian, M. McGarry, M. Reisslein, Offline and online multithread polling in long-reach PONs: A
critical evaluation, IEEE/OSA Journal of Lightwave Technology 31 (12) (2013) 2018–2228.
[23] X. Bai, C. M. Assi, A. Shami, On the fairness of dynamic bandwidth allocation schemes in Ethernet passive
optical networks, Computer Communications 29 (11) (2006) 2123–2135.
[24] A. R. Dhaini, C. M. Assi, M. Maier, A. Shami, Dynamic wavelength and bandwidth allocation in hybrid
TDM/WDM EPON networks, IEEE/OSA Journal of Lightwave Technology 25 (1) (2007) 277–286.
[25] X. Bai, A. Shami, Y. Ye, Delay analysis of Ethernet passive optical networks with quasi-leaved polling and
gated service scheme, in: Proceeding of International Conference on Access Networks & Workshops
(AccessNets), 2007.

17
[26] F. Aurzada, M. Scheutzow, M. Herzog, M. Maier, M. Reisslein, Delay analysis of Ethernet passive optical
networks with gated service, IEEE/OSA Journal of Optical Communications and Networking 7 (1) (2008)
25–41.
[27] S. Bharati, P.Saengudomlert, Analysis of mean packet delay for dynamic bandwidth allocation algorithms
in EPONs, IEEE/OSA Journal of Lightwave Technology 28 (23) (2010) 3454–3462.
[28] Q. Cui, T. Ye, T. Lee, W. Guo, W. Hu, Stability and delay analysis of EPON registration protocol, IEEE
Transactions on Communications 62 (7) (2014) 2478–2493.
[29] G. Kramer. (No date). Generator of Self-Similar Traffic (version 3) [Online] Available:
http://glenkramer.com/ucdavis/code/trf_gen3.html [Accessed 28 February 2014]
[30] I. White, M. Rogge, K. Shrikhande, L. Kazovsky, A summary of the HORNET project: a next-generation
metropolitan area network, IEEE Journal on Selected Areas in Communications 21 (9) (2003) 1478–1494.
[31] H. Song, B.-W. Kim, B. Mukherjee, Multi-thread polling: a dynamic bandwidth distribution scheme in
long-reach PON, IEEE Journal on Selected Areas in Communications 27 (2) (2009) 134–142.
[32] A. Helmy, H. Fathallah, H. T. Mouftah, Interleaved polling versus multi-thread polling for bandwidth
allocation in long-reach PONs, IEEE/OSA Journal of Optical Communications and Networking 4 (3) (2012)
210–218.
[33] J. Ahmed, J. Chen, L. Wosinska, B. Chen, B. Mukherjee, Efficient inter-thread scheduling scheme for
long-reach passive optical networks, IEEE Communications Magazine 51 (2) (2013) 35–43.
[34] C.-H. Chang, N. M. Alvarez, P. Kourtessis, R. M. Lorenzo, J. M. Senior, Full-Service MAC Protocol for
Metro-Reach GPONs, IEEE/OSA Journal of Lightwave Technology 28 (7) (2010) 1016–1022

18
Tables:

Table 1. DBA algorithms classified by grant scheduling framework

Representative
Type The timing when the OLT makes access decision
schemes
Online On the receipt of a REPORT from any ONU, IPACT[8]
schedule only that ONU
[17]

Offline On the receipt of REPORTs from all ONUs, schedule Sort-DBA[11]

all ONUs
ONU Load On receipt of a REPORT from any ONU, schedule DBA2-FE[14-15]
Status that ONU immediately if the REPORT is less than a
guaranteed minimum. Otherwise, schedule the ONU
until REPORTs from all ONUs have been received
Double Phase ONUs are divided into two groups. Within each DPA[12]
Polling group, a schedule is triggered by the receipt of
REPORTs from all ONUs in this group

19
Table 2. Notation table of system parameters

Symbol Description
Bandwidth request of ONU i in one cycle (traffic load dependent)
i
Brequest

protocol
DHLD Average packet delay time under network heavy load condition
(protocol dependent)
protocol
DMLD Average packet delay time under network medium load condition
(protocol dependent)
H report Packet size of a MPCP report message

H USR Average size of the un-used slot remainder (USR) of an ONU

Lmin Minimum guaranteed bandwidth (= 24.875Kbytes, defined in

Sort-DBA)
N Number of ONUs

Q Buffer size in an ONU

RU Upstream link rate from an ONU to OLT

RTT The round trip time between an ONU and OLT

protocol, HLD Cycle time under network heavy load condition (protocol
Tcycle
dependent) Cycle time defined as the time span during which all
ONUs’ upstream data transmission is done
protocol , MLD Cycle time under network medium load condition (protocol
Tcycle
dependent)

TDBA Time for DBA operation process at OLT during each cycle

TG Guard time between two consecutive transmission windows

Tidle Upstream link idle time due to stop-and-wait polling

TONU Grant processing time at an ONU

Time used for data transmission during a cycle for an ONU when
protocol, HLD
TTxData the network is heavy-loaded (protocol dependent)

protocol Maximum transmission window size of an ONU (protocol

W Max
dependent)
protocol Upstream link utilization when network is heavy loaded (protocol
U HLD
dependent)

20
Table 3. Simulation setup parameters

Simulation parameters Value

Number of ONUs 16

RU (data rate of the upstream link, Gbps) 1

RD (data rate of the access link, Mbps) 100

RTT (round trip time, ȝs) 200

Q (buffer size of ONU, Mega Bytes) with FIFO queue discipline 10

TG (guard time between consecutive TX windows, ȝs) 1

TDBA (DBA processing time, ȝs) neglected

TONU (grant processing time at the ONU, ȝs) neglected

IPACT—LS, 15.5
DBA2—FE,
Wmax (maximum transmission window size, Kilo Bytes) DPA
SORT—DBA, 24.875
AP—SORT—DBA
Pareto self similar with Hurst
Traffic trace parameter H of 0.8
Poisson

Packet size distribution MCI backbone with OC-3 links

Figure List:

Fig. 1. Typical access network based on tree EPON topology

Fig. 2. Un-used slot remainder (USR) in a heavily loaded ONU
Fig. 3. MPCP REPORT message format with additive polling messages
Fig. 4. Pseudo code for Additive-Polling-With-Sort-DBA()
Fig. 5. Pseudo code for Sort-DBA-Light-Load()
Fig. 6. Operation of AP-Sort-DBA
Fig. 7. Polling table update operation at OLT
Fig. 8. (a) Average packet delay (b) Normalized average packet delay
Fig. 9. (a) Average queue size using Pareto traffic (b) packet loss ratio (c) Average queue size using
Poisson traffic
Fig. 10. (a) Average USR number per cycle (b) Utilization
Fig. 11. (a) Average vacant time per cycle (b) Average cycle time

21
Figure_1
Figure_2
Figure_3
Figure_6
Figure_7
Figure_4
Figure_5
Figure_8
Figure_9
Figure_10
Figure_11