# Optimum Transmission Window for EPONs with Gated-Limited Service

Huanhuan Huang, Tong Ye, Tony T. Lee, and Weisheng Hu This work was supported
in part by the National Science Foundation of China under Grant 61571288,
Grant 61671286, and Grant 61433009, and in part by the Open Research Fund of
Key Laboratory of Optical Fiber Communications (Ministry of Education of
China).The authors are with the State Key Laboratory of Advanced Optical
Communication Systems and Networks, Shanghai Jiao Tong University, Shanghai
200240, China (email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>wshu@sjtu.edu.cn).

###### Abstract

This paper studies the Ethernet Passive Optical Network (EPON) with gated-
limited service. The transmission window (TW) is limited in this system to
guaranteeing a bounded delay experienced by disciplined users, and to
constrain malicious users from monopolizing the transmission channel. Thus,
selecting an appropriate TW size is critical to the performance of EPON with
gated-limited service discipline. To investigate the impact of TW size on
packet delay, we derive a generalized mean waiting time formula for M/G/1
queue with vacation times and gated-limited service discipline. A
distinguished feature of this model is that there are two queues in the buffer
of each optical network unit (ONU): one queue is inside the gate and the other
one is outside the gate. Furthermore, based on the Chernoff bound of queue
length, we provide a simple rule to determine an optimum TW size for gated-
limited service EPONs. Analytic results reported in this paper are all
verified by simulations.

###### Index Terms:

Ethernet Passive Optical Network (EPON), Gated-Limited Service, M/G/1.

##  I Introduction

The ever-growing Internet traffic generated by emerging services, including
video on demand, remote e-learning, and online gaming, continuously
exacerbates the last mile bottleneck problem in recent decades [1]. Ethernet
Passive Optical Network (EPON) has been considered as an attractive solution
to this problem due to its low cost, large capacity and ease of upgrade to
higher bit rates [2]. It has been deployed widely in many access networks such
as Fiber-To-The-Home (FTTH), Fiber-To-The-Building (FTTB) and Fiber-To-The-
Curb (FTTC) [3, 4, 5].

A typical EPON is plotted in Fig. 1. An EPON is a point-to-multipoint network,
where one optical line terminal (OLT) in the central office is connected to
multiple optical network units (ONUs) located at the users’ premises via an
optical passive splitter. In the downstream direction, the OLT broadcasts the
packets to all the ONUs, and each ONU only accepts the packets destined to it.
In the upstream direction, the OLT schedules the ONUs to share the bandwidth
in a time division multiplexing (TDM) manner. The OLT assigns transmission
windows (TWs) to each ONU through sending GATE messages in a round-robin
fashion. Upon receiving the GATE message, the ONU transmits upstream data in
the allocated TW. The number of packets that the ONU can send during a TW is
called the TW size in this paper. After data transmission, the ONU generates a
REPORT message to inform the OLT of its buffer status [2]. The TWs of two
successive ONUs are separated by a guard time to avoid data overlapping. The
sizes of TWs that the OLT allocates to each ONU depend on the service
discipline that the OLT adopts.

Figure 1: Upstream transmission in the EPON.

The gated service discipline has been widely studied in previous works [6, 7,
8, 9, 10, 11, 12, 13]. In the gated service, each ONU is authorized to
transmit the amount of data that it requests in the REPORT [14]. Thus, the
gated service may lead to the phenomenon called the capture effect [15], when
an ONU with heavy traffic monopolizes the upstream channel for a long time and
transmits excessive amounts of data. The capture effect will impose a large
delay to other ONUs and thus impair the quality of service (QoS) of other
ONUs. With the gated-limited service, the EPON users have to sign a service
level agreement (SLA) with the network operator to specify the upstream
traffic rate, and the OLT typically sets a limit of the maximum TW size to
guarantee the QoS of each ONU according to their signed SLAs.

The selection of the maximum TW size is a critical choice in the gated-limited
service EPON. On one hand, if the maximum TW size is set too small, the
backlog of the ONUs cannot be cleaned up quickly and the upstream bandwidth is
wasted by a large number of guard times and REPORT messages. In this case, the
ONU will suffer from a large delay. On the other hand, if the maximum TW size
is set too large, the capture effect cannot be suppressed effectively. An
extreme case is that the gated-limited service discipline will change to the
gated service discipline when the limit goes to infinity.

In existing literature, only a few previous works have studied the selection
of the maximum TW size via simulations. The impact of the maximum TW size on
delay performance of an ONU is discussed in [16], in which the author points
out that the maximum TW size for each ONU can be fixed based on the SLA, but
doesn’t provide any concrete scheme for the selection of the maximum TW size.
The aim of our paper is to develop a systematic method to select a proper
maximum TW size for gated-limited service EPONs.

The upstream transmission process of each ONU can be described by a vacation
queuing system, in which each TW of the ONU is considered as a busy period
while the time between two successive TWs of the ONU is treated as a vacation
period. In general, the modeling of a vacation queuing system with limited
service discipline is quite difficult [17]. In the gated-limited service EPON,
the number of packets that an ONU can transmit in a TW is limited by the
maximum TW size. Thus, before the transmission of an arrival packet, it may
have to wait multiple vacations, which is typically difficult to analyze [18].

###  I-A Previous Works Related to EPONs with Gated-Limited Service

The exhaustive type $k$-limited vacation queuing systems were studied in [19,
20, 21, 22], where the server takes a vacation when either a queue has been
emptied or a predefined number of $k$ customers have been served during the
visit. In [19], the distributions of queue length, waiting time and busy
period were obtained by using the embedded Markov chain and a combination of
the supplementary variables and sample biasing techniques. In [20, 21], the
authors used matrix-analytic techniques to iteratively calculate the queue
length distribution. In [22], a polling system with two priority queues and
$k$-limited service discipline was analyzed, where the high priority queue is
served with queue length dependent service time while the low priority queue
is served with constant service time. The high priority queue length
distribution at departure instants were derived by the embedded Markov chain.
However, these models cannot be directly applied to gated-limited service
EPONs, in which the OLT only serves the packets that arrived before the last
REPORT message of an ONU up to a predefined number, regardless if the buffer
is empty or not.

The gated type $k$-limited service vacation queuing systems were considered in
[23, 24], where the server serves at most $k$ customers that present at a
queue upon visiting and then begins a vacation. A queuing model based on an
embedded Markov chain was developed in [23, 24] to derive the Laplace-
Stieltjes transforms of waiting time and busy period distributions, but the
computation is too complex to give a clear physical insight into the
performance of the entire system. To resolve this problem, a simple geometric
approach was proposed in [18] to obtain the mean waiting time, but this
approach can only solve a special case when the user is allowed to transmit
one packet in each busy period.

In exiting literature, a few works were devoted to the modeling of gated-
limited service EPONs. In [6], the authors gave an approximate expression of
mean waiting time for a gated-limited service (which is called limited service
in [6]) EPON under the assumption that the maximum TW size in terms of time
(instead of the number of packets) is quite large, which is actually similar
to analysis of the gated service EPON. In [8], an approximate mean delay of
gated-limited service EPONs is derived by using a discrete Markov chain, which
is invalid when traffic load is high.

In summary, none of the previous works have obtained a useful formula of mean
waiting time for general gated-limited service EPONs where the maximum TW size
is finite and larger than one, and neither have they discussed how to select a
proper maximum TW size for each ONU of gated-limited service EPONs.

###  I-B Our Approach and Contributions

In this paper, we analyze the polling process of EPONs with gated-limited
service discipline. Our goal is to develop an insightful model to describe the
delay performance of gated-limited service EPONs, and to find a systematic
method of selecting the maximum TW size for each ONU based on the SLA.

First, we adopt the geometric approach described in [18] to derive the mean
waiting time of an M/G/1 queue with vacations and gated-limited service. A key
step is to calculate the mean number of whole vacations, excluding the
residual vacation, experienced by an arrival before it receives service. The
computation of this key parameter is based on an innovative approach that
establishes the connection between the mean number of whole vacations and the
first and second moments of the number of packets served in a busy period. A
distinguished feature of this model is that there are two queues in the buffer
of each ONU: one queue is inside the gate and the other one is outside the
gate.

Next, we apply the Chernoff bound of queue length to select the optimum TW
size. According to the SLA, the delay performance of an ONU shouldn’t be
influenced by the TW size limit if its traffic rate does not exceed the
subscribed rate. Thus, the criterion of selecting the optimum TW size is to
choose the smallest integer that makes the probability of queue length
exceeding the TW size limit negligible. That is, when an ONU operates in the
subscripted region, its buffer can be emptied with a high probability at the
end of every busy period. Otherwise, the ONU will suffer from a large delay
when the input traffic rate exceeds the subscribed rate. Our specific
contributions are summarized as follows:

  1. 1.

We derive a generalized formula of mean waiting time for M/G/1 queue with
vacation time and gated-limited service discipline, which includes the mean
waiting times of two queues.

  2. 2.

We provide a simple rule to determine a proper optimum TW size for ONUs of the
gated-limited service EPON based on their SLAs, which is proved to be
effective by simulations.

The remainder of this paper is organized as follows. In Section II, we
demonstrate the capture effect and provide an overview of the polling process
between the OLT and ONUs of a gated-limited service EPON. In Section III, we
derive the mean waiting time of the M/G/1 queue with vacation time and gated-
limited service discipline, and apply the result to ONUs of the EPON. Section
IV discusses the method of selecting the optimum TW size and the delay
performance of gated-limited service EPONs under the selected TW size. Section
V draws the conclusion.

##  II Motivation and Overview

Figure 2:  Mean waiting time of two ONUs under different service disciplines:
(a) gated service and (b) gated-limited service ($M=4$).

An EPON can be considered as a polling system where a single server visits a
set of queues in a cyclic order. A service discipline is one of the three
policies, exhaustive service, gated service, and limited service, that specify
the criteria of the server when progressing to the next queue [25]. In a
polling system with exhaustive service discipline where the server serves a
queue until it becomes empty, the capture effect occurs when a heavily loaded
user transmits excessive amounts of data and monopolizes the channel for a
long time, such that other lightly loaded users suffer from prolonged waiting
times.

To alleviate this problem, current EPON systems adopt the gated service
discipline where the OLT only transmits the packets that are requested by the
ONU in the last REPORT message during a TW. However, the capture effect still
persists since the user with heavy traffic can report a large number of
packets to the OLT at the end of a TW to secure a large size TW in the next
cycle, which will lengthen the delays that other ONUs have to endure. This
problem can be completely solved by the gated-limited service discipline,
which is able to cap the TW size assigned to each ONU by a predefined value.

This point can be illustrated by using the example where two ONUs are
connected to the OLT, and each of them is equipped with an infinite buffer.
The service capacity of EPON is 1000 packets/ms. We assume that these two ONUs
have signed the same SLAs with the network operator, meaning that they
subscribe to the same upstream traffic rate (300 packets/ms) and have
identical TW sizes, 4. Suppose ONU 1 is a disciplined user with a fixed input
rate of 300 packets/ms according to the signed SLA, whereas ONU 2 is a
malicious user whose traffic input rate is more than 300 packets/ms. Their
mean waiting times versus the arrival rate of ONU 2 under the gated and gated-
limited service disciplines are plotted in Fig. 2 and 2, respectively.

With the gated service discipline, despite that the constant loading of ONU 1
is smaller than that of ONU 2, as Fig. 2 shows, the mean waiting time of ONU 1
is not only continuously increasing with the arrival rate of ONU 2, but also
is uniformly larger than that of the malicious user ONU 2. Moreover, it is
unbounded when the input traffic rate generated by ONU 2 reaches 700
packets/ms. In this case, 70 percent of bandwidth is monopolized by ONU 2.

On the other hand, with the gated-limited service discipline, each ONU can
transmit no more than 4 packets during each busy period in our example. Fig. 2
shows that once the arrival rate of ONU 2 exceeds the subscribed rate 300
packets/ms, it immediately suffers from a larger mean waiting time than ONU 1
and soon becomes unstable when the arrival rate is larger than 400 packets/ms
due to the limited TW size. The disciplined user ONU 1 enjoys a small mean
waiting time all the time, and it is immune to the malicious behavior of ONU
2. This example clearly shows that the EPON with gated-limited service
discipline can completely avoid the capture effect and provide a fair service
to disciplined users while penalizing malicious users.

In an EPON system with $N$ ONUs that adopts the gated-limited service
discipline, the packets waiting in the buffer of each ONU are divided into two
groups by a fictitious gate. The number of packets inside the gate is bounded
by the maximum TW size, denoted by $M$. An arrival packet first waits outside
the gate and then enters the gate before it can be transmitted. As Fig. 3
illustrates, the buffer status is represented by a two-tuple state $(n,m)$,
where $n$ is the number of packets waiting outside the gate, and $m$ is that
waiting inside the gate. The number $n$ increases by 1 upon a new arrival, and
$m$ decreases by 1 when a packet inside the gate begins to be transmitted by
the ONU.

Figure 3: Polling process of an EPON where $N=2$ and $M=3$.

Fig. 3 plots the polling process of an EPON, where $N=2$ and $M=3$. A 64-byte
GATE is employed by the OLT to notify an ONU about the start time and the
length of each allocated TW. Upon receiving the GATE message, the ONU
transmits all packets inside the gate during the TW. At the end of the TW, the
ONU sends a 64-byte REPORT to the OLT, which reports the number of packets
waiting outside the gate. According to the number $n$ stated in the REPORT,
the OLT decides the TW size for this ONU in the next cycle, which equals the
smaller of $M$ and $n$. Thus, the message REPORT offers the admission for
packets waiting outside the gate to enter the gate.

After the ONU 1 issued the first REPORT, as Fig. 3 shows, the buffer state
changes from $(2,0)$ to $(0,2)$, which means two packets entered the gate.
Then the ONU 1 becomes idle while the OLT polls the next ONU. When the OLT
finishes the polling of all other $(N-1)$ ONUs, it sends a GATE message to ONU
1 again to repeat the process. To avoid data overlapping induced by the clock
synchronization problem between the OLT and the ONUs [26], two successive TWs
are separated by a guard time. As Fig. 3 depicts, the constant interval $G$
includes the guard time and the transmission time of a REPORT.

The purpose of limiting the TW size is twofold: to guarantee a bounded delay
experienced by disciplined users, and to constrain malicious users from
monopolizing the transmission channel. With the gated-limited service
discipline, the TW size $M$ limits the maximum number of packets that can be
served in a busy period. The gated-limited service discipline cannot
effectively constrain malicious users if the TW size $M$ is too large, and it
may introduce longer than expected delays for disciplined users if $M$ is too
small. Therefore, selecting an appropriate maximum TW size $M$ is critical to
the performance of EPON with gated-limited service discipline. In the
following sections, we devise a queueing model to analyze the mean waiting
time of each ONU under the gated-limited service discipline, and provide a
rule to determine the proper TW size $M$ of an EPON. The notations used
throughout this paper are defined as follows for easy reference.

$N$

Number of ONUs

$M$

The maximum TW size

$G$

The guard time plus the transmission time of a REPORT

${\lambda}_{E}^{*}$

Subscribed traffic rate for all the ONUs

${\lambda}_{E}$

Arrival rate of all the ONUs

${\rho}_{E}$

Offered load to the EPON

$n_{i}$

Number of packets found waiting outside the gate of the buffer when the $i$-th
packet arrives

$m_{i}$

Number of packets found waiting inside the gate of the buffer when the $i$-th
packet arrives

$N_{i}$

Number of packets found waiting in the buffer when the $i$-th packet arrives,
${N}_{i}={m}_{i}+{n}_{i}$

$R_{i}$

Residual time seen by the $i$-th packet when it arrives during a busy period
or a vacation time in progress

$Y_{i}$

Duration of all the whole vacation times experienced by the $i$-th packet
before it gets service

$X_{i}$

Service time of the $i$-th packet

$W_{i}$

Waiting time of the $i$-th packet

##  III Modeling of EPONs with Gated-limited Service

In this section, we analyze the mean packet waiting time of an ONU in the EPON
with gated-limited service discipline. As Fig. 3 shows, an ONU is busy with
packet transmission during the TW, followed by a vacation period with a
duration that equals the sum of $NG$ and the TWs of other $(N-1)$ ONUs.
Therefore, at the end of each busy period, a predominate number of packets
that an ONU reports to the OLT attributes to the number of arrivals during the
vacation period before it. Hence, there are dependencies among TW sizes of
ONUs. However, in the analysis of multiple access systems, such as Aloha or
CSMA, this kind of dependency is weak and can be neglected when $N$ is large
[27, 28]. Thus, we can treat each ONU independently. We make the following
assumptions in the modeling of EPONs with gated-limited service:

  * A1.

All ONUs in the EPON are statistically identical.

  * A2.

The number of ONUs $N$ is large, such that the TWs of the ONUs can be
considered as i.i.d. random variables. In practice, the number of ONUs is
usually more than 16 in a typical EPON.

  * A3.

The packet arrival process of the EPON is Poisson, as is the arrival process
of each ONU.

  * A4.

The packets are transmitted in a first-in-first-out (FIFO) manner, and the
transmission times of the packets are i.i.d. random variables with a general
distribution.

  * A5.

The propagation delay between the OLT and an ONU is very small in currently
commercial EPONs, and can be ignored in the analysis.

Under these assumptions, each ONU can be considered as an M/G/1 queue with
vacations and gated-limited service. In Section III-A, we derive the mean
waiting time of this queuing system, which provides the key to analyze EPONs
with gated-limited service discipline in this paper.

###  III-A M/G/1 Queue with Vacations and Gated-Limited Service

We adopt the following notations in the analysis of the M/G/1 queue with
vacations and gated-limited service:

  1. (1)

the traffic arrival rate is $\lambda$,

  2. (2)

the service times of the packets $X_{1}$, $X_{2},\cdots$ are i.i.d. random
variables with the first moment $\overline{X}$ and the second moment
$\overline{X^{2}}$, and

  3. (3)

the vacation times $V_{1}$, $V_{2},\cdots$ are i.i.d. random variables with
the first moment $\overline{V}$ and the second moment $\overline{V^{2}}$.

Under the gated-limited service discipline, up to $M$ packets waiting outside
the gate will enter the gate at the end of each busy period, and they will be
served in the next busy period. After each busy period, the server takes a
vacation. When the vacation terminates, the server returns to serve the
packets if the buffer inside the gate is not empty; otherwise, the server
takes another vacation.

A cycle starts at the end of a busy period, and consists of a vacation period
followed by another busy period. As Fig. 4 illustrates, the $i$-th packet
$A_{i}$ may arrive at the system during a busy period or a vacation period.
The following definitions pertaining to busy periods will be adopted in the
derivation of mean waiting time of the packets:

$B$

A busy period.

$K=k$

The number of packets served in a busy period, where $k=0,1,2,\cdots,M$.

$B_{k}$

A busy period, during which $k$ packets are served, where $k=0,1,2,\cdots,M$
($B_{0}$ happens when a vacation finishes while the buffer inside the gate is
empty).

$b_{k}$

The probability that a busy period is a $B_{k}$.

$P_{k}$

The probability that a packet is served in a $B_{k}$, where
$k=0,1,2,\cdots,M$.

${\Delta}_{i}$

The number of packets served ahead of the $i$-th packet $A_{i}$ in the same
busy period.

We need the following two lemmas to facilitate the derivation of the mean
waiting time of packets.

######  Lemma 1.

The probability that the $i$-th packet $A_{i}$ is served in a busy period
$B_{k}$ is given by

$P_{k}=\frac{k{b}_{k}}{\overline{K}}$ (1)

###### Proof:

Suppose there are ${\theta}_{k}$ busy periods $B_{k}$ during a time interval
$\left[0,T\right]$, where $k=0,1,2,\cdots,M$. The probability $b_{k}$ that a
busy period is a $B_{k}$ is defined by

$b_{k}=\lim_{T\to\infty}\frac{{\theta}_{k}}{\sum_{k=0}^{M}{\theta}_{k}}$

During the time interval $\left[0,T\right]$, the number of packets that are
served in all ${\theta}_{k}$ busy periods $B_{k}$ is $k{\theta}_{k}$, and the
total number of packets served in the interval $\left[0,T\right]$ is
$\sum_{k=1}^{M}k{\theta}_{k}$. It follows that the probability $P_{k}$ that
the $i$-th packet $A_{i}$ is served in a busy period $B_{k}$ can be obtained
as follows

$\displaystyle P_{k}$
$\displaystyle=\lim_{T\to\infty}\frac{k{\theta}_{k}}{\sum_{k=1}^{M}{k{\theta}_{k}}}=\lim_{T\to\infty}\frac{k{\times}\frac{{\theta}_{k}}{\sum_{k=0}^{M}{\theta}_{k}}}{\sum_{k=1}^{M}k{\times}\frac{{\theta}_{k}}{\sum_{k=0}^{M}{\theta}_{k}}}$
$\displaystyle=\frac{kb_{k}}{\sum_{k=1}^{M}kb_{k}}=\frac{kb_{k}}{\overline{K}}.$

∎

######  Lemma 2.

The mean number of packets served ahead of the $i$-th packet $A_{i}$ in the
same busy period is given by

$E\left[{\Delta}_{i}\right]=\frac{\overline{K^{2}}-\overline{K}}{2\overline{K}}.$
(2)

###### Proof:

Conditioning on the event that packet $A_{i}$ is served in a busy period
$B_{k}$, we have

$\displaystyle E\left[{\Delta}_{i}\right]$
$\displaystyle=\sum_{k=1}^{M}E\left[{\Delta}_{i}|A_{i}~{}is~{}served~{}in~{}a~{}B_{k}\right]P_{k}$
$\displaystyle=\sum_{k=1}^{M}\frac{0+1+\cdots+(k-1)}{k}\frac{kb_{k}}{\overline{K}}$
$\displaystyle=\sum_{k=1}^{M}\frac{\left(k^{2}-k\right)b_{k}}{2\overline{K}}=\frac{\overline{K^{2}}-\overline{K}}{2\overline{K}}.$

∎

Figure 4: Waiting time of the $i$-th packet $A_{i}$, where $M=3$.

As Fig. 4 shows, it may take the server several busy periods to clear all
packets waiting in the buffer ahead of packet $A_{i}$. Since the server can
only transmit up to $M$ packets in each busy period, before the starting of
service, the waiting time of packet $A_{i}$ includes the following components:

  1. (1)

The time to complete current service or current vacation. When the packet
$A_{i}$ arrives, the residual time, either residual service time or residual
vacation time, seen by $A_{i}$ is denoted by $R_{i}$.

  2. (2)

The service times of all $N_{i}$ packets found waiting in the buffer when
$A_{i}$ arrives.

  3. (3)

Besides residual vacation time, the duration of the whole vacation times
experienced by $A_{i}$ before the starting of service is denoted by $Y_{i}$.

It follows from the similar argument given in [18], we have

$\overline{W}=\overline{R}+N_{Q}\overline{X}+\overline{Y},$ (3)

and

$\overline{R}=E\left[R_{i}\right]=\frac{\lambda\overline{X^{2}}}{2}+\frac{\left(1-\rho\right)\overline{V^{2}}}{2\overline{V}},$
(4)

where $N_{Q}=E\left[N_{i}\right]=\lambda\overline{W}$ is the mean queue
length, and $\rho=\lambda\overline{X}$ is the traffic load. The key to derive
the mean waiting time (3) is the third term
$\overline{Y}=E\left[{Y_{i}}\right]$, which is given in the proof of the
following theorem.

######  Theorem 1.

The mean waiting time of an M/G/1 queue with vacations and gated-limited
service discipline is given by

$\overline{W}=\frac{\frac{\lambda\overline{X^{2}}}{2}+\frac{\left(1-\rho\right)\overline{V^{2}}}{2\overline{V}}+\left[1-\frac{\left(1+\rho\right)\left(\overline{K^{2}}-\overline{K}\right)}{2M\overline{K}}-\frac{\lambda\overline{V}}{M}\right]\overline{V}}{1-\rho-\frac{\lambda\overline{V}}{M}}.$
(5)

###### Proof:

Suppose the system is in state $(n_{i},m_{i})$ when packet $A_{i}$ arrives,
meaning that the number of packets waiting in the buffer are $n_{i}$ outside
and $m_{i}$ inside the gate. After $A_{i}$ arrives, all $m_{i}$ packets inside
the gate are sent out during the first busy period, at the end of which the
first $M$ of the $n_{i}$ packets enters the gate. The packet $A_{i}$ enters
the gate at the end of the
$\left(\lfloor{\left.{n}_{i}\middle/M\right.}\rfloor+1\right)$-th busy period,
and is sent out during the
$\left(\lfloor{\left.{n}_{i}\middle/M\right.}\rfloor+2\right)$-th busy period.
That is, the number of whole vacations that $A_{i}$ has to experience before
the starting of service is $\lfloor{\left.{n}_{i}\middle/M\right.}\rfloor+1$,
where $\lfloor{x}\rfloor$ is the largest integer smaller than $x$.

For example, as Fig. 4(a) shows, the state of system is $(n_{i},m_{i})=(4,2)$
upon the arrival of $A_{i}$ and $M$ is three, thus $A_{i}$ has to wait for
$\lfloor{\left.{n}_{i}\middle/M\right.}\rfloor+1=\lfloor{4/3}\rfloor+1=2$
whole vacation times in the buffer before it can be transmitted. It’s the same
as that in Fig. 4(b). Thus, we have

$\overline{Y}=\left(1+E\left[\left\lfloor{\frac{n_{i}}{M}}\right\rfloor\right]\right)\overline{V}.$
(6)

In the $\left(\lfloor{\left.{n}_{i}\middle/M\right.}\rfloor+2\right)$-th busy
period, the number of packets transmitted ahead of $A_{i}$ is given by
${\Delta}_{i}=n_{i}-{\lfloor}{\frac{n_{i}}{M}}{\rfloor}M$. For example, as
Fig. 4(a) shows, packet $A_{i}$ is the second packet served in the third busy
period. Since $n_{i}=4$ upon the arrival of $A_{i}$ and $M=3$, it follows that
${\Delta}_{i}=n_{i}-{\lfloor}{\frac{n_{i}}{M}}{\rfloor}M=4-3=1$. However, in
Fig. 4(b), there is no packet transmitted before $A_{i}$ in the third busy
period since the system state is $(n_{i},m_{i})=(3,3)$ when $A_{i}$ arrives,
and in this case
${\Delta}_{i}=n_{i}-{\lfloor}{\frac{n_{i}}{M}}{\rfloor}M=3-3=0$. Therefore, by
definition, we have

$E\left[{\left\lfloor\frac{n_{i}}{M}\right\rfloor}\right]=\frac{E\left[{n_{i}}\right]-E\left[{{\Delta}_{i}}\right]}{M}.$
(7)

Notice that the mean queue length $N_{Q}$ is the sum of the mean number of
packets waiting outside the gate $\overline{n}=E[n_{i}]$ and that waiting
inside the gate $\overline{m}=E[m_{i}]$. It follows that

$\overline{n}=E[n_{i}]=N_{Q}-\overline{m}.$ (8)

Since the packet $A_{i}$ is moved into the gate at the end of the
$\left(\lfloor{\left.{n}_{i}\middle/M\right.}\rfloor+1\right)$-th busy period
and served in the
$\left(\lfloor{\left.{n}_{i}\middle/M\right.}\rfloor+2\right)$-th busy period,
the waiting time of $A_{i}$ inside the gate, denoted as $W_{in}^{i}$, includes
the vacation time $V$ between these two busy periods, and the total service
time of ${\Delta}_{i}$ packets transmitted ahead of $A_{i}$ in the
$\left(\lfloor{\left.{n}_{i}\middle/M\right.}\rfloor+2\right)$-th busy period.
Thus, the mean waiting time of $A_{i}$ inside the gate is given by

$\overline{W}_{in}=E\left[{W_{in}^{i}}\right]=\overline{V}+E\left[{{\Delta}_{i}}\right]\overline{X}.$

From Little’s Law and Lemma 2, we obtain the following mean number of packets
waiting inside the gate:

$\overline{m}=\lambda\overline{W}_{in}=\lambda\overline{V}+\frac{\rho\left({\overline{K^{2}}-\overline{K}}\right)}{2\overline{K}}.$
(9)

The theorem is established by combining (3)-(4) and (6)-(9). ∎

Suppose the distribution of service time $X$ is given. The evaluation of the
mean waiting time (5) requires the first two moments of the vacation time $V$
and the number of packets $K$ transmitted in a busy period. Intuitively, they
are related to each other because the random variable $K$ is dependent on the
number of arrivals during the vacation time $V$. Focusing on the application
of the above theorem to EPONs, we will discuss the relationship between the
first two moments of $V$ and $K$ in the next Section III-B.

###  III-B Mean Packet Waiting Time of EPONs with Gated-Limited Service
Discipline

In this subsection, we apply the result of Theorem 1 to calculate the mean
packet waiting time of an ONU in the gated-limited service EPON, where the
rate of the traffic input to the network is ${\lambda}_{E}$ and to each ONU is
$\lambda=\left.{\lambda}_{E}\middle/N\right.$. We assume that the distribution
of the packet transmission time $X$ is given.

1) _Moments of Vacation Time V of An ONU:_ An ONU is busy with probability
$\rho=\lambda\overline{X}$ and idle with probability $1-\rho$. The mean busy
period of an ONU is given by

$\overline{B}=E[B]=\frac{\rho\overline{V}}{1-\rho}.$ (10)

In an EPON with $N$ ONUs, the vacation time of an ONU is equal to the TWs of
other $(N-1)$ ONUs plus $NG$. According to our assumption A2, the TWs are
i.i.d. random variables. By definition, we have

$\overline{V}=(N-1)\overline{B}+NG=(N-1)\frac{\frac{{\rho}_{E}}{N}\overline{V}}{1-\frac{{\rho}_{E}}{N}}+NG,$

where ${\rho}_{E}={\lambda}_{E}\overline{X}=N\rho$ is the offered load to the
EPON. After some reconfigurations, the first moment of the vacation time $V$
for an ONU is given by

$\overline{V}=\frac{N-{\rho}_{E}}{1-{\rho}_{E}}G.$ (11)

Similarly, the second moment of the vacation time $V$ for an ONU is defined as
follows

$\overline{V^{2}}={\overline{V}}^{2}+{\sigma}_{V}^{2}={\overline{V}}^{2}+(N-1){\sigma}_{B}^{2},$
(12)

where ${\sigma}_{V}^{2}$ and ${\sigma}_{B}^{2}$ are the variances of $V$ and
$B$, respectively. Recall that $B_{k}$ is a busy period during which $k$
packets are transmitted. It follows that $B_{k}=\sum_{i=1}^{k}{X_{i}}$, in
which $X_{1},X_{2},\cdots,X_{k}$ are i.i.d. random variables. Let
$X^{*}(\theta)$ and $B^{*}(\theta)$ be the Laplace-Stieltjes transforms of the
probability density function (PDF) of the service time $X$ and the busy period
$B$, respectively. They are related as follows:

$\displaystyle B^{*}(\theta)$
$\displaystyle=E\left[{e^{-{\theta}B}}\right]=E\left[{E\left[{e^{-{\theta}B}|B_{k}}\right]}\right]=\sum_{k=0}^{M}E\left[{e^{-{\theta}B_{k}}}\right]b_{k}$
$\displaystyle=\sum_{k=0}^{M}\left({\prod_{i=1}^{k}E\left[{e^{-{\theta}X_{i}}}\right]}\right)b_{k}=\sum_{k=0}^{M}{\left[{X^{*}(\theta)}\right]}^{k}{b_{k}}$
$\displaystyle=F\left[{X^{*}(\theta)}\right],$

where $F(z)=\sum_{k=0}^{M}{b_{k}}z^{k}$ is the generating function of $b_{k}$.
Therefore, the variance of the busy period ${\sigma}_{B}^{2}$ can be obtained
by

$\begin{split}{\sigma}_{B}^{2}&=B^{*\prime\prime}(0)-{\left[-B^{*\prime}(0)\right]}^{2}\\\
&=F^{\prime\prime}(1){\left[X^{*\prime}(0)\right]}^{2}+F^{\prime}(1)X^{*\prime\prime}(0)-{\left[F^{\prime}(1)X^{*\prime}(0)\right]}^{2}\\\
&=\left({\overline{K^{2}}-\overline{K}}\right){\overline{X}}^{2}+\overline{K}\overline{X^{2}}-{\left({\overline{K}\overline{X}}\right)}^{2}\\\
&={\overline{X}}^{2}\left({\overline{K^{2}}-{\overline{K}}^{2}}\right)+\overline{K}\left({\overline{X^{2}}-{\overline{X}}^{2}}\right).\end{split}$
(13)

Substituting (13) into (12), we obtain the following expression of
$\overline{V^{2}}$:

$\overline{V^{2}}={\overline{V}}^{2}+(N-1)\left[{{\overline{X}}^{2}\left({\overline{K^{2}}-\overline{K}}\right)+\overline{K}\left({\overline{X^{2}}-\overline{X}}\right)}\right].$
(14)

From (11) and (14), we know from (5) that the mean packet waiting time of an
ONU can now be determined by the first two moments $\overline{K}$ and
$\overline{K^{2}}$ of the number of packets transmitted in a busy period.

2) _Moments of Number of Packets K Transmitted in A Busy Period:_ The first
moment of $K$ can be easily derived from (10) and (11), and given as follows:

$\overline{K}=\frac{\overline{B}}{\overline{X}}=\frac{\lambda\overline{V}}{1-\rho}=\frac{\frac{{\lambda}_{E}}{N}\overline{V}}{1-\frac{{\rho}_{E}}{N}}=\frac{{\lambda}_{E}G}{1-{\rho}_{E}}.$
(15)

The derivation of the second moment $\overline{K^{2}}$, however, has to resort
to the discrete time Markov chain embedded in the epochs at the end of busy
periods. As Fig. 5 shows, the upstream transmission process of an ONU is a
sequence of cycles. For example, at the end of cycle $j-1$ and the beginning
of cycle $j$, the ONU reports its queue length, denoted as $l_{j}$, to the
OLT. According to this report, the OLT determines the size of the TW in cycle
$j$, denoted as $k_{j}$, as follows: $k_{j}=M$ if ${l_{j}}\geq{M}$, and
$k_{j}=l_{j}$, if $l_{j}<M$. That is, the TW size $k_{j}$ in cycle $j$ is
determined by the queue length $l_{j}$ at the start of cycle $j$ and given as
follows

$k_{j}=l_{j}-{\left({l_{j}-M}\right)}^{+},$ (16)

where ${\left(l_{j}-M\right)}^{+}{\triangleq}\max{\left\\{l_{j}-M,0\right\\}}$
is the number of reported packets that are not transmitted in cycle $j$.

Figure 5: Upstream transmission process of an ONU, where $M=3$.

Let $q_{n}=\lim_{j\to\infty}Pr\\{l_{j}=n\\}$. Recall that $b_{k}$ is the
probability that $k$ packets are served in a busy period. According to (16),
we have

$b_{k}=\left\\{\begin{array}[]{cl}q_{k},&k=0,1,\cdots,M-1\\\
1-\sum_{k=0}^{M-1}q_{k},&k=M\end{array}\right.$ (17)

Thus, the second moment of $K$ can be obtained based on the distribution of
the queue length $q_{n}$ as follows

$\overline{K^{2}}=\sum_{k=0}^{M}k^{2}b_{k}=\sum_{k=0}^{M-1}k^{2}q_{k}+M^{2}\left({1-\sum_{k=0}^{M-1}q_{k}}\right).$
(18)

On the other hand, the queue length $l_{j+1}$ at the start point of cycle
$j+1$ is determined by the number of packets $k_{j}$ transmitted during the
busy period of cycle $j$ and the number of arrivals $a_{j}$ during cycle $j$.
Thus, from (16), the queue length at the start point of each cycle satisfies
the following Lindley’s equation:

$l_{j+1}=l_{j}-k_{j}+a_{j}={\left({l_{j}-M}\right)}^{+}+a_{j}.$ (19)

Let $h_{n}=\lim_{j\to\infty}Pr\\{a_{j}=n\\}$ be the probability that there are
$n$ arrivals during a cycle time $C$. We immediately derive the following
equilibrium equation from (19):

$q_{n}=\sum_{i=0}^{M-1}q_{i}h_{n}+\sum_{i=M}^{M+n}q_{i}h_{n+M-i},$

from which we obtain the generating function of queue length:

$Q(z){\triangleq}\sum_{n=0}^{\infty}q_{n}z^{n}=\frac{\left[{\sum_{i=0}^{M-1}q_{i}\left({z^{M}-z^{i}}\right)}\right]H\left(z\right)}{z^{M}-H(z)},$
(20)

where $H\left(z\right){\triangleq}\sum_{n=0}^{\infty}h_{n}z^{n}$ is the
generating function of $h_{n}$.

According to our assumption A3 that the packet arrival process of each ONU is
a Poisson process, the distribution $h_{n}$ is completely determined by the
cycle time distribution. Let $c(t)$ be the PDF of the cycle time $C$. We have

$H(z)=\sum_{n=0}^{\infty}\left[{\int_{0}^{\infty}\frac{{\left({{\lambda}t}\right)}^{n}}{n!}e^{-{\lambda}t}c\left(t\right)dt}\right]z^{n}=C^{*}\left[{{\lambda}\left(1-z\right)}\right].$
(21)

A cycle consists of a vacation period and a busy period, which means that the
cycle time is the sum of $NG$ and the duration of the TWs of $N$ ONUs, which
are i.i.d. random variables according to our assumption A2. It follows that
the distribution of cycle time is approximately a Gaussian distribution
according to the central limit theorem [29]. The Laplace-Stieltjes transform
of the cycle time distribution is given by

$C^{*}(\theta)=exp\left[{-{\mu}_{C}\theta+\frac{1}{2}{\sigma}_{C}^{2}{\theta}^{2}}\right],$
(22)

where the mean cycle time can be obtained from (11), and is given as follows:

${\mu}_{C}=\frac{\overline{V}}{1-\rho}=\frac{\frac{\left(N-{\rho}_{E}\right)G}{1-{\rho}_{E}}}{1-\frac{{\rho}_{E}}{N}}=\frac{NG}{1-{\rho}_{E}},$
(23)

while the variance of the cycle time $C$ is determined by the variance of busy
period (13):

${\sigma}_{C}^{2}=N{\sigma}_{B}^{2}=N\left[{{\overline{X}}^{2}\left({\overline{K^{2}}-{\overline{K}}^{2}}\right)+\overline{K}\left({\overline{X^{2}}-{\overline{X}}^{2}}\right)}\right].$
(24)

We know that the second moment $\overline{K^{2}}$ in (18) is coupled to the
queue length probability $q_{n}$, for $n=0,1,\cdots,M-1$. For a given
$\overline{K^{2}}$, according to Rouche’s theorem and Lagrange’s theorem [23],
we can first solve $q_{n}~{}(n=0,1,\cdots,M-1)$ from (20)-(24), and then
update $\overline{K^{2}}$ by substituting $q_{n}$ into (18). Repeatedly
applying this iterative procedure, we can obtain the value of
$\overline{K^{2}}$ and then obtain the mean waiting time (5) of an ONU by
combining (11), (14), (15), and $\overline{K^{2}}$. The procedure that
numerically calculates $\overline{K^{2}}$ and the mean waiting time is given
in APPENDIX A. In the next section, we seek a systematic rule to select the
optimum TW size for each ONU of the EPON that satisfies practical operational
requirements of EPONs with gated-limited service.

##  IV Optimum Transmission Window Size

As we mentioned in Section I, EPON users usually have to sign a SLA with the
network operator to specify the upstream traffic rate. Suppose all ONUs are
statistically identical, and each ONU subscribes to a SLA with a maximum
traffic rate $\left.{{\lambda}_{E}^{*}}\middle/{N}\right.$, where
${\lambda}_{E}^{*}$ is the total subscribed traffic rate of all the ONUs,
which is less than $\left.1\middle/\overline{X}\right.$ . An ONU is a
disciplined user if its input traffic rate is in the admissible region
$\lambda={\lambda}_{E}/N\in\left[{0,{\lambda}_{E}^{*}/N}\right]$. Otherwise,
it is considered a malicious user. An EPON system is _regular_ if all the ONUs
are disciplined users. In this section, we first describe the methodology and
procedure to select an optimum TW size $M$ for a given traffic rate
${\lambda}_{E}^{*}/N$. We then discuss the stability and delay performance of
EPON system under this selected TW size $M$.

As we mentioned in Section II, the purpose of limiting the TW size $M$ is
twofold: to guarantee that the mean delays experienced by disciplined users
are bounded, and to penalize malicious users. With gated-limited service
discipline, the TW size $M$ limits the maximum number of packets that can be
served in a busy period. Ideally, a proper TW size $M$ ensures that all
packets arrived at a disciplined ONU during a cycle time can be completely
served in the next busy period. To achieve this goal, the probability that the
queue length at the beginning of a cycle exceeds the limit $M$ should be kept
very small. Thus, the criterion for the selection of TW size $M$ is given by

$Pr\\{l{\geq}M\\}=\lim_{j\to\infty}Pr\\{l_{j}{\geq}M\\}{\leq}\varepsilon,$
(25)

for some positive $\varepsilon\ll 1$, when
$\lambda={\lambda}_{E}/N\in\left[0,{\lambda}_{E}^{*}/N\right]$. In the
following, we show that an optimum TW size $M$ that satisfies the criterion
(25) can be selected by using the Chernoff bound of queue length.

###  IV-A Chernoff Bound of Queue Length

The Chernoff bound of the tail distribution of queue length $l$ at the
beginning of a cycle is given as follows [30]:

$Pr\\{l{\geq}{\mu}_{l}+t\\}=Pr\\{z^{l}{\geq}z^{{\mu}_{l}+t}\\}{\leq}\frac{E\left[z^{l}\right]}{z^{{\mu}_{l}+t}},$
(26)

for any $z>1$, where $E[z^{l}]=Q(z)$ is the generating function of the queue
length distribution and ${\mu}_{l}=E[l]$ is the mean queue length.

Suppose all the ONUs are disciplined users with input traffic rate
$\lambda={\lambda}_{E}/N\in\left[{0,{\lambda}_{E}^{*}/N}\right]$, and the TW
size $M$ satisfies the criterion (25), then each time the queue length
reported by an ONU should be typically smaller than $M$ with a high
probability $1-\varepsilon$. It follows that equations (16) and (19) will
respectively degenerate to the following approximate equations:

$\displaystyle l_{j}$ $\displaystyle{\approx}k_{j},$ (27) $\displaystyle
l_{j+1}$ $\displaystyle{\approx}a_{j},$ (28)

which implies that the following generating functions of $l_{j}$, $k_{j}$ and
$a_{j}$ are approximately equal:

$Q(z){\approx}F(z){\approx}H(z).$ (29)

Thus, according to (21)-(24), we have

$\displaystyle Q(z){\approx}H(z)=$ $\displaystyle
exp\left[{-{\lambda}{\mu}_{C}(1-z)+\frac{1}{2}{\lambda}^{2}{\sigma}_{C}^{2}(1-z)^{2}}\right]$
$\displaystyle=$ $\displaystyle
exp\left\\{-\frac{{\lambda}_{E}G\left(1-z\right)}{1-{\rho}_{E}}+\left[{\overline{X}}^{2}\big{(}{\overline{K^{2}}-{\overline{K}}^{2}}\big{)}\right.\right.$
$\displaystyle\left.\left.+\overline{K}\big{(}{\overline{X^{2}}-{\overline{X}}^{2}}\big{)}\right]\frac{{\lambda}_{E}^{2}(1-z)^{2}}{2N}\right\\}.$
(30)

In this equation, the second moment of the number of packets served in each
busy period can be obtained by

$\overline{K^{2}}=F^{\prime\prime}(1)+F^{\prime}(1){\approx}H^{\prime\prime}(1)+H^{\prime}(1).$
(31)

Substituting (30) into (31), we have

$\displaystyle\overline{K^{2}}=$
$\displaystyle{\left({\frac{{\lambda}_{E}G}{1-{\rho}_{E}}}\right)}^{2}+\frac{{\rho}_{E}^{2}}{N}\left[{\overline{K^{2}}-{\left({\frac{{\lambda}_{E}G}{1-{\rho}_{E}}}\right)}^{2}}\right]$
$\displaystyle+\frac{{\lambda}_{E}^{3}G}{N\left({1-{\rho}_{E}}\right)}\left({\overline{X^{2}}-{\overline{X}}^{2}}\right)+\frac{{\lambda}_{E}G}{1-{\rho}_{E}},$

which yields

$\overline{K^{2}}={\left({\frac{{\lambda}_{E}G}{1-{\rho}_{E}}}\right)}^{2}+\frac{\frac{{\lambda}_{E}^{3}G}{N\left({1-{\rho}_{E}}\right)}\left({\overline{X^{2}}-{\overline{X}}^{2}}\right)+\frac{{\lambda}_{E}G}{1-{\rho}_{E}}}{1-\frac{{\rho}_{E}^{2}}{N}}.$
(32)

Substituting (32) into (30), we obtain $Q(z)$ in the _regular_ case as
follows:

$\displaystyle Q(z){\approx}$ $\displaystyle
exp\left[-\frac{{\lambda}_{E}G}{1-{\rho}_{E}}(1-z)+\frac{{\lambda}_{E}^{3}G\overline{X^{2}}}{2\left({1-{\rho}_{E}}\right)\left({N-{\rho}_{E}^{2}}\right)}{(1-z)}^{2}\right].$
(33)

The mean and variance of queue length $l$ are respectively given as follows:

${\mu}_{l}=Q^{\prime}\left(1\right)={\lambda}{\mu}_{C}=\frac{{\lambda}_{E}G}{1-{\rho}_{E}},$
(34)

and

$\displaystyle{\sigma}_{l}^{2}$
$\displaystyle=Q^{\prime\prime}(1)+Q^{\prime}(1)-{\left[{Q^{\prime}(1)}\right]}^{2}={\lambda}^{2}{\sigma}_{C}^{2}+{\lambda}{\mu}_{C}$
$\displaystyle=\frac{{\lambda}_{E}^{3}G\overline{X^{2}}}{\left({1-{\rho}_{E}}\right)\left({N-{\rho}_{E}^{2}}\right)}+\frac{{\lambda}_{E}G}{1-{\rho}_{E}}.$
(35)

It follows from the first equation of generating function of queue length in
(30), the Chernoff bound (26) is given by

$\displaystyle Pr\\{l{\geq}{\mu}_{l}+t\\}{\leq}$ $\displaystyle
exp\left[{-\left({{\mu}_{l}+t}\right){\log}z+{\lambda}{\mu}_{C}\left(z-1\right)+\frac{1}{2}{\lambda}^{2}{\sigma}_{C}^{2}{(z-1)}^{2}}\right],$

for any $z>1$. Substituting $t=M-{\mu}_{l}$ into the above Chernoff bound, the
criterion (25) can be fulfilled if $M$ is the smallest integer that satisfies
the following inequality:

$\displaystyle Pr\\{l{\geq}M\\}{\leq}$
$\displaystyle\inf_{z>1}\left\\{exp\left[{-M{\log}z+{\lambda}{\mu}_{C}\left(z-1\right)+\frac{1}{2}{\lambda}^{2}{\sigma}_{C}^{2}{\left(z-1\right)}^{2}}\right]\right\\}\\!{\leq}{\varepsilon},$
(36)

where ${\lambda}{\in}\left[{0,{\lambda}_{E}^{*}/N}\right]$. We discuss the
procedure to find the optimum TW size $M^{*}$ that satisfies (36) in the next
subsection.

###  IV-B Optimum Transmission Window Size

Solving the optimum TW size $M^{*}$ from (36) involves a complicated
transcendental equation, therefore it can only be solved numerically. To
initialize the computation procedure, we provide a lower bound $M_{1}$ and an
upper bound $M_{2}$ of $M^{*}$ in the following theorem.

######  Theorem 2.

The optimum TW size $M^{*}$ that satisfies (36) is bounded by

$\left\lceil{{\mu}_{l}+\\!\lambda{\sigma}_{C}\sqrt{2\alpha}}\right\rceil\\!=\\!M_{1}{\leq}M^{*}{\leq}M_{2}\\!=\\!\left\lceil{{\mu}_{l}+\alpha+\\!\sqrt{{\alpha}^{2}+2\alpha{\sigma}_{l}^{2}}}\right\rceil$
(37)

where $\alpha=\log{{\varepsilon}^{-1}}$ and
$\lambda={\lambda}_{E}/N{\in}\left[{0,{\lambda}_{E}^{*}/N}\right]$.

$\blacksquare$

The proof of the above theorem is given in APPENDIX B. An accurate
approximation of the optimum TW size $M^{*}$ can be derived from the upper
deviation inequality of normal random variables. We know that the cycle time
$C$ approaches a normal random variable $\mathcal{N}(\mu_{C},\sigma_{C}^{2})$
when $N$ is large. The relation (28) indicates that the queue length at the
beginning of each cycle is approximately equal to the number of arrivals
during a cycle time $C$, or $l\sim{\lambda}C$. As expected, the mean queue
length $\mu_{l}$ given by (34) is the product of the arrival rate $\lambda$
and the mean cycle time $\mu_{C}$. It is also interesting to note that the
variance of the queue length $\sigma_{l}^{2}$ given by (35) is the sum of
$\lambda^{2}\sigma_{C}^{2}$ and the variance of a Poisson random variable with
parameter $\mu_{l}$. Thus, the queue length $l$ can be approximated by a
normal random variable $\mathcal{N}\left(\mu_{l},\sigma_{l}^{2}\right)$ that
is discretized by a Poisson process with rate $\lambda$. That is, we adopt the
following approximation of queue length distribution:

$q_{n}{\cong}q_{n}^{\prime}=\frac{1}{\sqrt{2\pi}\sigma_{l}}\int_{n-\frac{1}{2}}^{n+\frac{1}{2}}e^{-\frac{{\left(x-\mu_{l}\right)}^{2}}{2\sigma_{l}^{2}}}dx.$
(38)

As Fig. 6 shows, the bigger the gap between these two distributions, the
smaller the probability $q_{n}$, where $q_{n}$ is obtained through the inverse
transform of $Q(z)$ in (33). We use the same set of parameters, including the
number of ONUs $N=32$, a guard time and a REPORT message transmission time
$G=1.512{\mu}s$, the first and second moments of service time
$\overline{X}=1{\mu}s,\overline{X^{2}}=1{{\mu}s}^{2}$, in all figures of this
subsection.

Figure 6: Probability distribution $q_{n}$ and $q_{n}^{\prime}$ with
$\lambda=21.875$ packets/ms.

It is well-known that any normal random variable
$X{\sim}\mathcal{N}(\mu,\sigma^{2})$ satisfies the following upper deviation
inequality [31]:

$Pr\\{X{\geq}\mu+t\\}{\leq}exp\left[{-\frac{t^{2}}{2{\sigma}^{2}}}\right],$

for $t{\geq}0$. Since the distribution of queue length $l$ is close to that of
the normal random variable $\mathcal{N}\left(\mu_{l},\sigma_{l}^{2}\right)$,
from the above inequality, the optimum TW size $M^{*}$ can be estimated by the
smallest integer $\hat{M}$ that satisfies the following relation:

$Pr\\{{l{\geq}\hat{M}}\\}{\leq}exp\left[{-\frac{{\left(\hat{M}-\mu_{l}\right)}^{2}}{2\sigma_{l}^{2}}}\right]{\leq}\varepsilon,$

and it is explicitly given by

$\hat{M}=\left\lceil{{\mu}_{l}+\sigma_{l}\sqrt{2\alpha}}\right\rceil.$ (39)

The following inequality immediately follows from (35) and (39):

$\left\lceil{{\mu}_{l}+\lambda{\sigma}_{C}\sqrt{2\alpha}}\right\rceil{\leq}\hat{M}{\leq}\left\lceil{{\mu}_{l}+\alpha+\sqrt{{\alpha}^{2}+2\alpha{\sigma}_{l}^{2}}}\right\rceil.$

That is, the approximation $\hat{M}$ of the optimum TW window size $M^{*}$
also lies between the two bounds $M_{1}$ and $M_{2}$.

As we mentioned before, the optimum TW size $M^{*}$ that satisfies the
inequality (36) can only be solved numerically from the following equation:

$\displaystyle f\left(t,z^{*}\right)=$ $\displaystyle
exp\left[\\!-\\!\left(\mu_{l}+t\right)\log{z^{*}}\\!+\\!\lambda\mu_{C}\left(z^{*}-1\right)\\!+\\!\frac{1}{2}{\lambda}^{2}\sigma_{C}^{2}{\left(z^{*}-1\right)}^{2}\right]\\!=\\!\varepsilon,$

where $z^{*}$ is obtained from the proof of theorem 2 in APPENDIX B and given
as follows:

$z^{*}\\!=\\!\frac{\sqrt{{\left({\lambda\mu_{C}-{\lambda}^{2}\sigma_{C}^{2}}\right)}^{2}+4\left(\mu_{l}+t\right){\lambda}^{2}\sigma_{C}^{2}}-\left({\lambda\mu_{C}-{\lambda}^{2}\sigma_{C}^{2}}\right)}{2{\lambda}^{2}\sigma_{C}^{2}}.$
(40)

The following procedure is used to solve the optimum TW size $M^{*}$ that
satisfies the inequality (36).

  1. Step 1:

$\lambda=\lambda_{E}^{*}/N,M=\hat{M},low=M_{1},up=M_{2}$;

  2. Step 2:

$t=M-\mu_{l}$, calculate $z^{*}$ by (40);

  3. Step 3:

If $f\left(t,z^{*}\right)>\varepsilon$, $low=M$; else $up=M$;
/* If $f(t,z^{*})$ is too large, we update the lower bound of searching region
to decrease $f(t,z^{*})$, otherwise we update the upper bound. */

  4. Step 4:

If $\left\lceil{low}\right\rceil{<}\left\lceil{up}\right\rceil$,
$M=\left(low+up\right)/2$, go to Step 2;

  5. Step 5:

$M^{*}=\left\lceil{low}\right\rceil=\left\lceil{up}\right\rceil$, output
$M^{*}$.

In the practical operation of EPON, the parameter $\varepsilon$ can be
selected from the region $[0.001,0.1]$, which implies that the buffered
packets of an ONU can be emptied with a probability $1-\varepsilon$ between
0.9 to 0.999 at the end of every busy period. A too large $\varepsilon$ causes
a too small $M$ that impairs the delay performance of disciplined users. On
the other hand, a too small $\varepsilon$ causes a too large $M$ that cannot
effectively suppress the capture effect.

Fig. 7 and 7 respectively illustrate that the optimum TW size $M^{*}$, its
lower bound $M_{1}$, upper bound $M_{2}$, and approximation $\hat{M}$, vary
with the tail bound $\varepsilon$ and the subscribed traffic rate
$\lambda_{E}^{*}/N$ of each ONU. In these figures, we find that both
approximate and optimum TW sizes, $\hat{M}$ and $M^{*}$, are always bounded
between $M_{1}$ and $M_{2}$. Moreover, the approximation $\hat{M}$ is
uniformly smaller than $M^{*}$, which can be readily seen from the
distributions illustrated in Fig. 6. The convergence rate of normal
distribution $q_{n}^{\prime}$ is faster than that of $q_{n}$, thus a smaller
TW size is needed to achieve the same probability of tail distribution. In
spite of that, as Fig. 7 shows, the difference between $\hat{M}$ and $M^{*}$
is very small in the region $\varepsilon\in[0.001,0.1]$ of our interest in
practice. Besides, the selection of TW size is very sensitive to the traffic
rate subscribed by a user, as illustrated in Fig. 7, with the growth of
$\lambda_{E}^{*}/N$, the TW size also increases greatly.

Figure 7: TW sizes vary with tail bound $\varepsilon$ and subscribed traffic
rate $\lambda_{E}^{*}/N$ respectively: (a) TW sizes vs.$~{}\varepsilon$ where
$\lambda_{E}^{*}/N=21.875$ packets/ms and (b) TW sizes vs. $\lambda_{E}^{*}/N$
where $\varepsilon=0.05$.

The tail distribution of queue length, $\sum_{n=M}^{\infty}q_{n}$, and that of
approximation, $\sum_{n=M}^{\infty}q_{n}^{\prime}$, are plotted in Fig. 8
where each ONU inputs traffic with the rate of 21.875 packets/ms. In our
interested region $\varepsilon\in[0.001,0.1]$, the difference between the TW
sizes selected by tail distributions of $q_{n}$ and $q_{n}^{\prime}$ is quite
small. When their gap is large, such as in the area
$\varepsilon\in[10^{-5},10^{-4}]$, $\varepsilon$ would be extremely small and
far below the region of our interest in the practical operation of EPON.

Figure 8: Tail distributions of $q_{n}$ and $q_{n}^{\prime}$ with
$\lambda=21.875$ packets/ms.

For a fixed $\varepsilon=0.05$, as Fig. 8 shows, despite that $\hat{M}<M^{*}$,
the probability $Pr\\{l{\geq}\hat{M}\\}$ is still below $\varepsilon$, which
means the approximation $\hat{M}$ also satisfies the criterion (25). If the TW
size is set equal to the lower bound $M_{1}$, the criterion
$Pr\\{l{\geq}M\\}{\leq}\varepsilon$ could be violated and packets may
experience longer delay than expected. On the other hand, if the TW size is
set equal to the upper bound $M_{2}$, the criterion can be easily satisfied
because $Pr\\{l{\geq}M_{2}\\}$ is negligible in comparison with $\varepsilon$.
However, the upper bound $M_{2}$ would be too large to be an effective
constraint on malicious users. As a compromise, the approximation $\hat{M}$
can serve as a practical TW size for EPONs.

###  IV-C Stability and Delay Performance of EPON

In this subsection, we study the delay performance of disciplined ONUs in a
regular gated-limited service EPON with the TW size limit $M$ given by (39).
The gated service discipline is a special case of the gated-limited service
discipline with infinite TW size, thus the mean waiting time in gated service
is the lower bound of that in gated-limited service.

The EPON system with gated service is stable if the offered load $\rho$ of
each ONU is less than $1/N$, i.e. $\lambda<1/\left(N\overline{X}\right)$,
which guarantees that input packets will be transmitted steadily and their
mean waiting time, or mean queue length, is bounded. However, a bounded mean
queue length is not sufficient to guarantee that a regular EPON with gated-
limited service is stable due to the limitation of TW size $M$. From the mean
queue length formula (34) of an ONU, the stable condition of the gated-limited
service EPON is given by

$\mu_{l}=\lambda\mu_{C}=\lambda\cdot\frac{NG}{1-\rho_{E}}<M,$ (41)

where $\rho_{E}=N\rho=N\lambda\overline{X}$. After some algebraic
manipulation, a stable traffic rate $\lambda$ should be bounded by
$\hat{\lambda}$ that is defined as follows:

$\lambda<\hat{\lambda}=\frac{M}{N\left(M\overline{X}+G\right)}$ (42)

It s evident that when $M\to\infty$, $\hat{\lambda}\to
1/\left(N\overline{X}\right)$. Furthermore, the TW size limit $M$ is selected
based on criterion (25), which guarantees a very small probability
$\varepsilon$ that the queue length will exceed the limit $M$, this is a much
more stringent condition than the stable condition (41). Therefore, in a
regular EPON with gated-limited service, disciplined ONUs with input traffic
rate in the region $\lambda\in\left[0,\lambda_{E}^{*}/N\right]$ must be all
stable, which implies $\lambda_{E}^{*}/N{\leq}\hat{\lambda}$.

Figure 9: Variance of busy periods under different subscribed traffic rates
with $\varepsilon=0.05$: (a) $\lambda_{E}^{*}/N=9.375$ packets/ms and (b)
$\lambda_{E}^{*}/N=21.875$ packets/ms.

Figure 10: Mean waiting time of an ONU under different subscribed traffic
rates with $\varepsilon=0.05$: (a) $\lambda_{E}^{*}/N=9.375$ packets/ms and
(b) $\lambda_{E}^{*}/N=21.875$ packets/ms.

According to the conditions described above, the performance of an ONU in a
gated-limited service EPON can be characterized in the following three traffic
regions:

  1. 1)

Subscripted region $\lambda\in\left[0,\lambda_{E}^{*}/N\right]$. In the
subscripted region, the QoS of each ONU in terms of mean delay is guaranteed
by the SLA signed with the network operator.

  2. 2)

Overloaded region $\lambda\in\left(\lambda_{E}^{*}/N,\hat{\lambda}\right)$. If
an ONU inputs the packets with the rate higher than its subscripted rate and
in the overloaded region, the mean delay is impaired by the limit of the
maximum TW size $M$, but it is still bounded. This region provides an
adjustment period for the ONU to decrease its input traffic rate when the user
experiences a larger than expected delay.

  3. 3)

Saturated region
$\lambda\in\left[\hat{\lambda},\frac{1}{N\overline{X}}\right)$. In the
saturated region, the arrival rate is too high for the OLT to handle. The ONU
is unstable when the queue length outside the gate of the buffer becomes
unbounded.

In the subscripted region $\lambda\in\left[0,\lambda_{E}^{*}/N\right]$ or in
the overloaded region
$\lambda\in\left(\lambda_{E}^{*}/N,\hat{\lambda}\right)$, the mean waiting
time of an ONU can be calculated by the procedure described in APPENDIX A. In
the saturated region
$\lambda\in\left[\hat{\lambda},\frac{1}{N\overline{X}}\right)$, the mean
waiting time is unbounded.

The analytical results of mean waiting time in these traffic regions are
verified by simulations. We consider a 1G EPON with $N=32$ statistically
identical ONUs, and assume that they have signed the same SLAs. The parameters
$G=1.512{\mu}s$, $\overline{X}=1{\mu}s$ and $\overline{X^{2}}=1{{\mu}s}^{2}$
are the same as those used in Section IV-B. Thus the service capacity of the
EPON is 1000 packets/ms, evenly divided into 31.25 packets/ms for each ONU.
Two scenarios are considered in our study, where each user subscribes to a low
traffic rate of 9.375 packets/ms and a high traffic rate of 21.875 packets/ms
respectively. According to formula (39), for a fixed $\varepsilon=0.05$, we
should set the maximum TW size $M$ equal to 3 and 9 in respect to the above
two scenarios.

Fig. 9 and 9 illustrate the variance of busy periods for each ONU. It is
evident that the analytical result given in APPENDIX A is consistent with the
simulation result, which validates the accuracy of our analysis in Section
III. If we adopt the gated service discipline (i.e., $M$ is infinite), Fig. 9
shows that the variance of busy periods monotonically increases with arrival
rate up to infinity. However, with the gated-limited service discipline (i.e.,
$M$ is finite), the variance of busy periods approaches zero, because each ONU
transmits a constant number of $M$ packets in each busy period when the
arrival rate is high.

In the subscripted region, as shown in Fig. 10 and 10, the disciplined users
in the gated-limited service EPON experience the same mean waiting time as
that in gated service EPON. This desirable property is due to the criterion
$Pr\\{l{\geq}M\\}{\leq}\varepsilon$ of selecting the TW size , which is
sufficiently large to empty the buffered packets almost in every busy period.

In the overloaded region, the ONU will suffer a larger mean delay than
expected, which serves as a precaution measure for the ONU to reduce the
loading back to the subscripted region. If the ONU continues increasing the
input traffic rate to the saturated region, its mean delay tends to infinity,
and the service is collapsed to prevent its malicious behavior from impacting
the QoS of other disciplined users.

##  V Conclusion

In this paper, we consider an EPON with gated-limited service discipline as a
polling system. Each ONU of an EPON is modeled as an M/G/1 queue with
vacations and gated-limited service. A distinguished feature of this model is
that there are two queues in the buffer of each ONU: one queue is inside the
gate and the other one outside the gate. We extend the traditional geometric
approach to derive the Pollaczek-Khinchine formula of mean waiting time.
Moreover, the Chernoff bound method is applied to the selection of the optimum
TW size. The criterion of selecting the TW size $M$ is to guarantee that the
delay performances experienced by disciplined users are bounded, and to
constrain malicious users from monopolizing the transmission channel. For this
purpose, we devise a simple rule to determine a proper optimum TW size for
each ONU of the gated-limited service EPON based on their SLAs.

##  Appendix A iterative procedure of calculating mean waiting time
$\overline{W}$ and variance of busy periods $\sigma_{B}^{2}$

As analyzed in Section III, it is critical to obtain the second moment of the
number of packets served in a busy period $\overline{K^{2}}$ when calculating
the mean waiting time and variance of busy periods. However, the value of
$\overline{K^{2}}$ and that of distribution $q_{n}~{}(n=0,1,\cdots,M-1)$
depend on each other, and we can only solve them numerically.

According to Rouche’s theorem, the denominator of (20) has $M$ zeros inside
and on $|z|=1$, one of them is $z=1$. Then by Lagrange’s theorem [23], the
other $(M-1)$ zeros inside $|z|=1$ are given by

$z_{m}=\sum_{n=1}^{\infty}\left.\frac{e^{2{\pi}mni/M}}{n!}\frac{d^{n-1}}{dz^{n-1}}{\Big{[}H\big{(}z\big{)}\Big{]}}^{n/M}\right|_{z=0},$
(43)

for $m=1,2,\cdots,M-1$. Since $Q(z)$ is analytic in $|z|{\leq}1$, the
numerator of (20) must also be zero at $z=z_{m}$. Therefore,
$q_{n}~{}(n=0,1,\cdots,M-1)$ satisfy the following $(M-1)$ linear equations:

$\sum_{n=0}^{M-1}q_{n}\left(z_{m}^{M}-z_{m}^{n}\right)=0,~{}~{}m=1,2,\cdots,M-1.$
(44)

Another equation is given as follows by the condition $Q(1)=1$:

$\sum_{n=0}^{M-1}q_{n}\left(M-n\right)=M-\lambda\mu_{C}=M-\frac{\lambda_{E}G}{1-\rho_{E}}.$
(45)

Thus, if we know the expression of $H(z)$, we can solve
$q_{n}~{}(n=0,1,\cdots,M-1)$ by combining (43)-(45), then obtain
$\overline{K^{2}}$ based on (18), which is

$\overline{K^{2}}=\sum_{n=0}^{M-1}n^{2}q_{n}+M^{2}\left({1-\sum_{n=0}^{M-1}q_{n}}\right).$

However, the expression of $H(z)$ is instead dependent on $\overline{K^{2}}$.
Therefore, given a calculation accuracy $\delta$, we can numerically solve
$\overline{K^{2}}$ through the following iteration procedure:

  1. Step 1:

$\overline{K^{2}}=0$;

  2. Step 2:

Calculate $H(z)$ by combining (15), (21)-(24);

  3. Step 3:

Solve $z_{m},m=1,2,\cdots,M-1$ by (43);

  4. Step 4:

Solve $q_{n},n=0,1,\cdots,M-1$ by combining (44) and (45);

  5. Step 5:

If
$\left|\sum_{n=0}^{M-1}n^{2}q_{n}+M^{2}\left(1-\sum_{n=0}^{M-1}q_{n}\right)-\overline{K^{2}}\right|>\delta$,
$\overline{K^{2}}=\sum_{n=0}^{M-1}n^{2}q_{n}+M^{2}\left(1-\sum_{n=0}^{M-1}q_{n}\right)$,
go to Step 2;

  6. Step 6:

Output $\overline{K^{2}}$.

Then, we can easily obtain the variance of busy periods for an ONU by
substituting $\overline{K^{2}}$ and (15) into (13), and the mean waiting time
by combining (5), (11), (14), (15) and $\overline{K^{2}}$.

##  Appendix B proof of theorem 2

Define the following function:

$f\left(t,z\right)\\!=\\!exp\Big{[}-\big{(}\mu_{l}+t\big{)}{\log}z\\!+\\!\lambda\mu_{C}\big{(}z-1\big{)}\\!+\\!\frac{1}{2}{\lambda}^{2}\sigma_{C}^{2}{\big{(}z-1\big{)}}^{2}\Big{]},$
(46)

where $z>1$ and $t{\geq}0$. We know that the following inequality holds for
all $x{\geq}0$:

$-x{\leq}-{\log}\left(1+x\right){\leq}-\left(x-\frac{1}{2}x^{2}\right).$ (47)

Let $x=z-1$, and apply (47) to (46), then we have the following inequality:

$f_{1}(t,z){\leq}f(t,z){\leq}f_{2}(t,z),$ (48)

where the two functions $f_{1}(t,z)$ and $f_{2}(t,z)$ are defined as follows:

$f_{1}(t,z)=exp\Big{[}-t\big{(}z-1\big{)}+\frac{1}{2}{\lambda}^{2}\sigma_{C}^{2}{\big{(}z-1\big{)}}^{2}\Big{]},$
(49)

and

$f_{2}(t,z)=exp\Big{[}-t\big{(}z-1\big{)}+\frac{1}{2}\big{(}\sigma_{l}^{2}+t\big{)}{\big{(}z-1\big{)}}^{2}\Big{]}.$
(50)

Take the derivatives of (46), (49) and (50), we obtain

$\displaystyle-\frac{\mu_{l}+t}{z^{*}}+\lambda\mu_{C}+{\lambda}^{2}\sigma_{C}^{2}\left(z^{*}-1\right)$
$\displaystyle=0,$ (51)
$\displaystyle-t+{\lambda}^{2}\sigma_{C}^{2}\left(z_{1}-1\right)$
$\displaystyle=0,$ (52)

and

$-t+\left(\sigma_{l}^{2}+t\right)\left(z_{2}-1\right)=0.$ (53)

It follows from (48), the following inequalities should hold:

$\displaystyle\inf_{z>1}f_{1}(t,z)$
$\displaystyle=f_{1}(t,z_{1}){\leq}f_{1}(t,z^{*}){\leq}f(t,z^{*}),$ (54)
$\displaystyle\inf_{z>1}f(t,z)$
$\displaystyle=f(t,z^{*}){\leq}f(t,z_{2}){\leq}f_{2}(t,z_{2}).$ (55)

Combining (54) and (55), the following expression can be obtained from $z_{1}$
and $z_{2}$ given by (52) and (53) respectively,

$\displaystyle f_{1}(t,z_{1})$
$\displaystyle=exp\left[-\frac{t^{2}}{2{\lambda}^{2}\sigma_{C}^{2}}\right]{\leq}f(t,z^{*})$
$\displaystyle{\leq}exp\left[-\frac{t^{2}}{2\left(\sigma_{l}^{2}+t\right)}\right]=f_{2}(t,z_{2}).$
(56)

Let $t^{*}$, $t_{1}$ and $t_{2}$ be the solutions that respectively satisfy
the following three equations:

$exp\left[-\frac{t_{1}^{2}}{2{\lambda}^{2}\sigma_{C}^{2}}\right]=f(t^{*},z^{*})=exp\left[-\frac{t_{2}^{2}}{2\left(\sigma_{l}^{2}+t_{2}\right)}\right]=\varepsilon.$

Then, according to (56), we have

$\displaystyle
exp\left[-\frac{{t^{*}}^{2}}{2{\lambda}^{2}\sigma_{C}^{2}}\right]{\leq}f(t^{*},z^{*})=exp\left[-\frac{t_{1}^{2}}{2{\lambda}^{2}\sigma_{C}^{2}}\right]$
$\displaystyle=exp\left[-\frac{t_{2}^{2}}{2\left(\sigma_{l}^{2}+t_{2}\right)}\right]{\leq}exp\left[-\frac{{t^{*}}^{2}}{2\left(\sigma_{l}^{2}+t^{*}\right)}\right].$
(57)

Since those exponential functions in (57) are monotonically decreasing with
$t$, we have

$t_{1}{\leq}t^{*}{\leq}t_{2}.$ (58)

Substituting $t=M-\mu_{l}$ into (58), we obtain

$M_{1}{\leq}M^{*}{\leq}M_{2}.$ (59)

Hence, the smallest integer $M_{1}$ that satisfies the following inequality is
a lower bound of $M^{*}$:

$exp\left[-\frac{{\left(M_{1}-\mu_{l}\right)}^{2}}{2{\lambda}^{2}\sigma_{C}^{2}}\right]{\leq}\varepsilon,$

and it can be explicitly expressed as follows:

$M_{1}=\left\lceil\mu_{l}+\lambda\sigma_{C}\sqrt{2\log\varepsilon^{-1}}\right\rceil=\left\lceil\mu_{l}+\lambda\sigma_{C}\sqrt{2\alpha}\right\rceil.$
(60)

Similarly, the smallest integer $M_{2}$ that satisfies the following
inequality is an upper bound of $M^{*}$:

$exp\left[-\frac{{\left(M_{2}-\mu_{l}\right)}^{2}}{2\left({\lambda}^{2}\sigma_{C}^{2}+M_{2}\right)}\right]{\leq}\varepsilon,$

and it can be given as follows:

$\displaystyle M_{2}$
$\displaystyle=\left\lceil\mu_{l}+\log\varepsilon^{-1}\\!+\\!\sqrt{{\left(\log\varepsilon^{-1}\right)}^{2}\\!+\\!2\log\varepsilon^{-1}\left(\mu_{l}+\lambda^{2}\sigma_{C}^{2}\right)}\right\rceil$
$\displaystyle=\left\lceil\mu_{l}+\alpha+\sqrt{{\alpha}^{2}+2\alpha\sigma_{l}^{2}}\right\rceil.$
(61)

We obtain (37) by combining (59)-(61).

## References

  * [1] G. Kramer, B. Mukherjee, and G. Pesavento, “Ethernet PON (EPON): Design and Analysis of an Optical Access Network,” _Photonic Network Communications_ , vol. 3, no. 3, pp. 307–319, 2001. [Online]. Available: http://dx.doi.org/10.1023/A:1011463617631
  * [2] G. Kramer, B. Mukherjee, and A. Maislos, _Ethernet passive optical networks_. New York: Wiley, 2003.
  * [3] H. Shinohara, “Broadband access in Japan: Rapidly growing FTTH market,” _IEEE Communications Magazine_ , vol. 43, no. 9, pp. 72–78, 2005.
  * [4] G. Keiser, _FTTX: concepts and applications_. Hoboken, New Jersey: John Wiley & Sons, 2006, vol. 91.
  * [5] L. Hutcheson, “FTTx: Current status and the future,” _IEEE Communications Magazine_ , vol. 46, no. 7, 2008.
  * [6] S. Bharati and P. Saengudomlert, “Analysis of mean packet delay for dynamic bandwidth allocation algorithms in EPONs,” _Journal of Lightwave Technology_ , vol. 28, no. 23, pp. 3454–3462, 2010.
  * [7] S. Bhatia, D. Garbuzov, and R. Bartos, “Analysis of the gated IPACT scheme for EPONs,” in _Communications, 2006. ICC’06. IEEE International Conference on_ , vol. 6. IEEE, 2006, pp. 2693–2698.
  * [8] B. Lannoo, L. Verslegers, D. Colle, M. Pickavet, M. Gagnaire, and P. Demeester, “Analytical model for the IPACT dynamic bandwidth allocation algorithm for EPONs,” _Journal of optical networking_ , vol. 6, no. 6, pp. 677–688, 2007\.
  * [9] F. Aurzada, M. Scheutzow, M. Herzog, M. Maier, and M. Reisslein, “Delay analysis of Ethernet passive optical networks with gated service,” _Journal of Optical Networking_ , vol. 7, no. 1, pp. 25–41, 2008.
  * [10] X. Bai, A. Shami, and Y. Ye, “Delay analysis of Ethernet passive optical networks with quasi-leaved polling and gated service scheme,” in _Access Networks & Workshops, 2007. AccessNets’ 07. Second International Conference on_. IEEE, 2007, pp. 1–8.
  * [11] S. Miyata, K.-i. Baba, K. Yamaoka, and H. Kinoshita, “Exact mean packet delay analysis for long-reach passive optical networks,” in _Global Communications Conference (GLOBECOM), 2015 IEEE_. IEEE, 2015, pp. 1–6.
  * [12] M. T. Ngo, A. Gravey, and D. Bhadauria, “A mean value analysis approach for evaluating the performance of EPON with gated IPACT,” in _Optical Network Design and Modeling, 2008. ONDM 2008. International Conference on_. IEEE, 2008, pp. 1–6.
  * [13] C. G. Park, D. H. Han, and K. W. Rim, “Packet delay analysis of symmetric gated polling system for DBA scheme in an EPON,” _Telecommunication Systems_ , vol. 30, no. 1, pp. 13–34, 2005.
  * [14] G. Kramer, B. Mukherjee, S. Dixit, Y. Ye, and R. Hirth, “Supporting differentiated classes of service in Ethernet passive optical networks,” _Journal of Optical Networking_ , vol. 1, no. 8, pp. 280–298, 2002.
  * [15] A. Capone, M. Gerla, and R. Kapoor, “Efficient polling schemes for bluetooth picocells,” in _Communications, 2001. ICC 2001. IEEE International Conference on_ , vol. 7. IEEE, 2001, pp. 1990–1994.
  * [16] G. Kramer, B. Mukherjee, and G. Pesavento, “IPACT: A dynamic protocol for an Ethernet PON (EPON),” _IEEE Communications Magazine_ , vol. 40, no. 2, pp. 74–80, 2002.
  * [17] E. Winands, I. Adan, G.-J. van Houtum, and D. Down, “A state-dependent polling model with $k$-limited service,” _Probability in the Engineering and Informational Sciences_ , vol. 23, no. 02, pp. 385–408, 2009.
  * [18] D. P. Bertsekas, R. G. Gallager, and P. Humblet, _Data networks_. Prentice-Hall International New Jersey, 1992, vol. 2.
  * [19] T. T. Lee, “M/G/1/N queue with vacation time and limited service discipline,” _Performance Evaluation_ , vol. 9, no. 3, pp. 181–190, 1989\.
  * [20] M. Van Vuuren and E. M. Winands, “Iterative approximation of $k$-limited polling systems,” _Queueing Systems_ , vol. 55, no. 3, pp. 161–178, 2007\.
  * [21] A. Al Hanbali, R. de Haan, R. J. Boucherie, and J.-K. van Ommeren, “Time-limited and $k$-limited polling systems: a matrix analytic solution,” in _Proceedings of the 3rd International Conference on Performance Evaluation Methodologies and Tools_. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), 2008, p. 17.
  * [22] M. B. Sikha and R. Manivasakan, “A two-queue finite-buffer polling model with limited service and state-dependent service times,” in _Electronics, Computing and Communication Technologies (IEEE CONECCT), 2014 IEEE International Conference on_. IEEE, 2014, pp. 1–6.
  * [23] H. Takagi, “Queueing analysis: a foundation of performance evaluation,” _Queueing systems vol. ii: computer applications_ , vol. 1, 1991.
  * [24] A. S. Alfa, “Vacation models in discrete time,” _Queueing Systems_ , vol. 44, no. 1, pp. 5–30, 2003.
  * [25] H. Takagi, “Queuing analysis of polling models,” _ACM Computing Surveys (CSUR)_ , vol. 20, no. 1, pp. 5–28, 1988.
  * [26] C.-C. Sue and H.-W. Cheng, “A fitting report position scheme for the gated IPACT dynamic bandwidth algorithm in EPONs,” _IEEE/ACM Transactions on Networking (TON)_ , vol. 18, no. 2, pp. 624–637, 2010.
  * [27] A. Munari, F. Rossetto, P. Mähönen, and M. Petrova, “On the Stability of a Full-Duplex Aloha Network,” _IEEE Communications Letters_ , vol. 20, no. 12, pp. 2398–2401, 2016.
  * [28] J.-B. Seo and H. Jin, “Stability Region of $p$-Persistent CSMA Systems,” _IEEE Communications Letters_ , 2016.
  * [29] J. Rice, _Mathematical statistics and data analysis_ , 3rd ed. Belmont, CA: Nelson Education, 2006.
  * [30] M. Mitzenmacher and E. Upfal, _Probability and Computing: Randomized algorithms and probabilistic analysis_. United Kingdom: Cambridge university press, 2005.
  * [31] S. Boucheron, G. Lugosi, and P. Massart, _Concentration inequalities: A nonasymptotic theory of independence_. United Kingdom: Oxford university press, 2013.


Other works also account for reward uncertainty, but assume that there is one true Markovian reward function that one can learn about, and one should use to evaluate trajectories [Hadfield-Menell et al., 2016, Desai, 2017, Chan et al., 2019]. A gap in the literature is work which tries to disambiguate between reward changes, and updates in belief regarding reward functions (which we discuss briefly in <Ref>).


# First-Passage-Driven Boundary Recession

B. De Bruyne  LPTMS, CNRS, Univ. Paris-Sud, Université Paris-Saclay, 91405
Orsay, France  J. Randon-Furling  SAMM, Université Paris 1 – FP2M (FR2036)
CNRS, 75013 Paris, France  MSDA, Mohammed VI Polytechnic University, Ben
Guerir 43150, Morocco  S. Redner  Santa Fe Institute, 1399 Hyde Park Rd.,
Santa Fe, New Mexico 87501, USA

###### Abstract

We investigate a moving boundary problem for a Brownian particle on the semi-
infinite line in which the boundary moves by a distance proportional to the
time between successive collisions of the particle and the boundary.
Phenomenologically rich dynamics arises. In particular, the probability for
the particle to first reach the moving boundary for the $n^{\text{th}}$ time
asymptotically scales as $t^{-(1+2^{-n})}$. Because the tail of this
distribution becomes progressively fatter, the typical time between successive
first passages systematically gets longer. We also find that the number of
collisions between the particle and the boundary scales as $\ln\ln t$, while
the time dependence of the boundary position varies as $t/\ln t$.

##  1 Introduction and Model

Moving boundary problems arise in materials that are near a first-order phase
transition (see, e.g., [1, 2, 3] for general introductions). Perhaps the most
familiar examples are the melting of ice that is immersed in water, or the
freezing of water on the surface of a lake when the ambient air suddenly cools
to a temperature $T<0^{\circ}$C at some initial time $t=0$. In the latter
case, a layer of ice starts growing on top of the water. The lower ice-water
interface remains at $0^{\circ}$C, while heat is conducted to the upper ice-
air interface and thence into the air. If the ice-air interface is defined to
be at spatial position $z=0$ and the ice-water interface is at $-L(t)$, then
to a first approximation, the temperature in the ice at vertical position $z$
is $T(z)=Tz/L$. As a result of this temperature gradient and the resulting
heat conduction, molecules of water at the interface freeze and join the ice
layer. Through this mechanism, the interface gradually grows downward at a
rate that is proportional to the temperature gradient in the ice; this gives
$L(t)\sim\sqrt{t}$.

Microscopically, heat conduction corresponds to the diffusion of phonons, with
interface motion occurring when the phonons first reach the interface. It is
in this sense that we can think of the motion of the boundary being controlled
by a first-passage process. Namely, whenever a diffusing particle reaches the
interface, the interface then moves by a specified amount. In [4], we studied
an idealization of this problem in a strictly one-dimensional geometry for the
two cases in which the interface recedes by a fixed distance or
multiplicatively, whenever a diffusing particle reaches the interface. After
each collision between the particle and the interface, the particle is
returned to its starting position and the process begins anew. This process
defines a simple first-passage resetting problem. This is a natural complement
to Poisson resetting, where a random walk or a diffusing particle is returned
to its starting position at some fixed rate[5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
15]. The consequences of Poisson resetting have been extensively investigated,
but first-passage resetting is much less explored thus far.

In the former case where the boundary moves by a fixed distance after each
first-passage event [4], we found that the number of collisions between the
particle and interface, as well as the position of the interface grew as
$t^{1/4}$. This should be compared to the $t^{1/2}$ growth of the number of
collisions when there is no resetting of the particle position. In the case of
multiplicative motion, the interface, which is initially located at $L$, moves
to $\alpha L$, $\alpha^{2}L$, $\alpha^{3}L$, after each successive collision.
Because this interface motion is rapid, the number of collisions now grows
only logarithmically in time. In spite of the small number of resetting
events, the interface position still grows as $t^{1/2}$ because later
collisions between the particle and interface leads to a large displacement of
the interface.

Figure 1: Illustration of the moving boundary (red line) in a semi-infinite
geometry due to first-passage resetting. Each time the particle reaches the
boundary, the boundary recedes by a distance $\alpha\tau_{i}+\epsilon$. The
successive first-passage times are denoted $\tau_{1},\tau_{2},\ldots$.

In this work, we study another natural scenario for first-passage resetting
where the boundary recedes by an amount that is proportional to the time
difference between successive encounters of the particle and the interface
(figure 1). Thus we investigate the dynamics of a one-dimensional Brownian
particle with diffusion coefficient $D$ that starts at the origin in a semi-
infinite geometry, with a boundary that is initially a distance $L_{0}$ from
the particle. This boundary remains fixed except for these instances when the
particle reaches it. When such an encounter happens, the boundary moves away
from the particle by a distance that is proportional to the first-passage time
between the previous and the current encounter. While there is no obvious
physical motivation for this model, the resulting phenomenology is quite rich
and perhaps has some fundamental implications.

As illustrated in figure 1, it is necessary to augment the recession distance
of the interface by a small additive amount to regularize a singular behavior
that arises when there is no cutoff. If the interface recedes by an amount
that is strictly linear in the first-passage time from the previous collision,
a pathology arises in which the particle can hit the interface infinitely
often in a finite time. That is, if the first-passage time is short, the time
to the next collision can be even shorter, ultimately leading to a
singularity. For a random walk on a lattice, there is no such pathology
because the minimum first-passage time cannot be less than the time for a
single step. To obviate the pathology in the case of continuum diffusion, we
define the recession distance of the interface to be equal to the first-
passage time from the previous collision plus a small cutoff $\epsilon$. Our
results are independent of this cutoff, but this cutoff is necessary to obtain
non-singular results.

Our primary results are the following: (a) The probability for the particle to
first reach the interface for the $n^{\text{t}h}$ time asymptotically decays
as $t^{-\beta_{n}}$, with $\beta_{n}=1+2^{-n}$. Thus the tail of the
$n^{\text{th}}$-passage probability becomes progressively fatter after each
collision. (b) The number of collisions between the particle and the interface
grows with time as $\ln\ln t$. This slow double logarithmic increase in the
number of collisions is reminiscent of the intriguing Khintchine iterated
logarithm law [16, 17, 18] for the extreme position of Brownian motion.
Finally, the position of the interface recedes according to $t/\ln t$. Once
again, even though collisions between the particle and the boundary are rare,
the widely separated collisions in time lead to a large displacement of the
boundary, so that its overall motion is nearly ballistic.

##  2 Successive-Passage Distributions

###  2.1 The second-passage distribution

We define $F_{n}(t\,|\,L_{0})$ as the probability that a diffusing particle,
which starts at $x=0$, _first_ reaches the boundary at $x=L_{0}$ for the
$n^{\text{th}}$ time at time $t$. When $n=1$, this quantity is just the first-
passage probability distribution for a Brownian motion to reach $x=L_{0}$ [19,
20]:

$\displaystyle F_{1}(t\,|\,L_{0})\equiv F(t\,|\,L_{0})=\frac{L_{0}}{\sqrt{4\pi
Dt^{3}}}\;e^{-L_{0}^{2}/4Dt}\,.$ (1)

Because of the convolution structure of the problem we are treating, it is
convenient to work in the Laplace domain. Thus we also introduce the Laplace
transform of $F_{1}(t\,|\,L_{0})$:

$\displaystyle\widetilde{F}_{1}(s\,|\,L_{0})=\int_{0}^{\infty}dt\,e^{-st}F_{1}(t\,|\,L_{0})=\,e^{-L_{0}\sqrt{s/D}}\equiv
e^{-L_{0}\,g_{1}(s)}\,,$ (2)

with $g_{1}(s)=\sqrt{s/D}$.

For the particle to first reach the boundary for the second time at time $t$,
it must first reach the boundary at an intermediate time $\tau_{1}$ and then
reach it one more time during the remaining time $\tau_{2}$, with
$t=\tau_{1}+\tau_{2}$. Since the boundary will have moved by a distance
$\tau_{1}+\epsilon$ after the first encounter (see figure 1), the second-
passage distribution is given by

$\displaystyle F_{2}(t\,|\,L_{0})$
$\displaystyle=\int_{0}^{\infty}d\tau_{1}\int_{0}^{\infty}d\tau_{2}\,F_{1}(\tau_{1}\,|\,L_{0})\times
F(\tau_{2}\,|\,\alpha\,\tau_{1}+\epsilon)\,\delta(t-\tau_{1}-\tau_{2})\,,$ (3)

Taking the Laplace transform gives

$\displaystyle\widetilde{F}_{2}(s\,|\,L_{0})$
$\displaystyle=\int_{0}^{\infty}d\tau_{1}\int_{0}^{\infty}d\tau_{2}\,F_{1}(\tau_{1}\,|\,L_{0})F(\tau_{2}\,|\,\alpha\,\tau_{1}+\epsilon)\,e^{-s\tau_{1}-s\tau_{2}}\,,$
$\displaystyle=\int_{0}^{\infty}d\tau_{1}\,F_{1}(\tau_{1}\,|\,L_{0})\,e^{-s\tau_{1}}\int_{0}^{\infty}d\tau_{2}\,F(\tau_{2}\,|\,\alpha\,\tau_{1}+\epsilon)\,e^{-s\tau_{2}}\,,$
(4a) where the second integral is simply the Laplace transform of the first-
passage distribution (2) with $L_{0}=\alpha\tau_{1}+\epsilon$. Using this
fact, we obtain $\displaystyle\widetilde{F}_{2}(s\,|\,L_{0})$
$\displaystyle=\int_{0}^{\infty}d\tau_{1}\,F_{1}(\tau_{1}\,|\,L_{0})\,e^{-s\tau_{1}}\;e^{-(\alpha\,\tau_{1}+\epsilon)\sqrt{s/D}}\,,$
$\displaystyle=e^{-\epsilon\sqrt{s/D}}\int_{0}^{\infty}d\tau_{1}\,F_{1}(\tau_{1}\,|\,L_{0})e^{-\tau_{1}\left(s+\alpha\sqrt{s/D}\right)}$
(4b) The integral is just the Laplace transform of the first-passage
distribution (2), but now evaluated at $s+\alpha\sqrt{s/D}$. Thus the second-
passage probability is
$\displaystyle\widetilde{F}_{2}(s\,|\,L_{0})=\exp[-\epsilon\sqrt{s/D}-L_{0}\frac{\sqrt{s+\alpha\sqrt{{s}/{D}}}}{\sqrt{D}}\bigg{]}\equiv
e^{-\epsilon\sqrt{s/D}-L_{0}\,g_{2}(s)}\,,$ (4c)

where

$\displaystyle
g_{2}(s)=\frac{\sqrt{s+\alpha\sqrt{s/D}}}{\sqrt{D}}=\frac{\sqrt{s+\alpha
g_{1}(s)}}{\sqrt{D}}\,.$

This expression for $\widetilde{F}_{2}(s\,|\,L_{0})$ cannot be Laplace
inverted analytically; however, in the relevant $s\to 0$ limit, its leading
behavior simplifies to

$\displaystyle\widetilde{F}_{2}(s\,|\,L_{0})\to\exp\left[-L_{0}\,\sqrt{\frac{\alpha}{D}}\left(\frac{s}{D}\right)^{1/4}\right]\,,$

which can be Laplace inverted. The result of this Laplace inversion is

$\displaystyle\frac{L_{0}}{96t^{5/4}}\left\\{\frac{24}{\Gamma\left(\frac{3}{4}\right)}\;_{0}F_{2}\left(;\frac{1}{2},\frac{3}{4};\frac{L_{0}^{4}}{256{t}}\right)-\sqrt{\frac{288}{\pi}}\frac{L_{0}}{t^{1/4}}\,_{0}F_{2}\left(;\frac{3}{4},\frac{5}{4};\frac{L_{0}^{4}}{256{t}}\right)\right.$
$\displaystyle\qquad\qquad\qquad\left.+\frac{3L_{0}^{3}}{t^{1/2}\Gamma\left(\frac{5}{4}\right)}\;_{0}F_{2}\left(;\frac{5}{4},\frac{3}{2};\frac{L_{0}^{4}}{256{t}}\right)-\frac{\sqrt{8}\,L_{0}^{3}}{\pi
t^{3/4}}\,_{1}F_{3}\left(1;\frac{5}{4},\frac{3}{2},\frac{7}{4};\frac{L_{0}^{4}}{256{t}}\right)\right\\}\,,$
(5)

where ${}_{p}F_{q}$ is the hypergeometric function. The salient feature of
this formidable-looking expression is that the second-passage probability
asymptotically decays as $t^{-5/4}$.

###  2.2 The $n^{\text{th}}$-passage distribution

By repeatedly applying the reasoning that led to (4c), the Laplace transform
of the $n^{\text{th}}$-passage probability is

$\displaystyle\widetilde{F}_{n}(s\,|\,L_{0})=\exp[-\epsilon\sum_{m=1}^{n-1}g_{m}(s)-L_{0}\,g_{n}(s)\bigg{]}\,,$
(6)

where, for $n\geq 2$, $g_{n}(s)$ is defined by the recursion

$\displaystyle g_{n}(s)=\frac{\sqrt{s+\alpha\,g_{n-1}(s)}}{\sqrt{D}}\,.$ (7)

Figure 2: The function $g_{n}(s)$ as a function of $s$ for different values of
$n$ with $\alpha=D=1$.

The analytical structure of $g_{n}(s)$ provides the key to understanding the
problem. In the limit $n\rightarrow\infty$ and $s$ fixed, $g_{n}(s)\rightarrow
g_{\infty}(s)$, where $g_{\infty}(s)$ satisfies
$g_{\infty}(s)=\sqrt{(s+\alpha\,g_{\infty}(s))/D}$. The solution for
$g_{\infty}(s)$ is

$\displaystyle
g_{\infty}(s)=\frac{1}{2}\left(\frac{\alpha}{D}+\sqrt{\frac{\alpha^{2}}{D^{2}}+\frac{4s}{D}}\right)\,.$
(8)

The function $g_{n}(s)$ is shown in figure 2 for several values of $n$, as
well as for $n=\infty$. Notice that $g_{n}(s)\to 0$ as $s\to 0$ for any finite
$n$, while $g_{\infty}(s\\!=\\!0)=\alpha/D$. Also, when $\alpha=0$, (6)
reduces to the $n^{\text{th}}$-resetting probability distribution that we
obtained previously [4].

For $s\to 0$ and fixed $n$, the recurrence (7) reduces to

$\displaystyle
g_{n}(s)\sim\left(\frac{\alpha}{D}\right)^{1-2^{1-n}}\;\left(\frac{s}{D}\right)^{2^{-n}}\,.$
(9)

Thus $g_{n}(s)$ becomes more singular as $n$ increases in such a way that
$g_{\infty}(0)=\alpha/D$. We now substitute the above limiting behavior in
(6), to give the small-$s$ expansion of the $n^{\text{th}}$ passage
distribution:

$\displaystyle\widetilde{F}_{n}(s\,|\,L_{0})\sim
1-L_{0}\left(\frac{\alpha}{D}\right)^{1-2^{1-n}}\left(\frac{s}{D}\right)^{2^{-n}}\,,\qquad
s\rightarrow 0\,.$ (10a) By a Tauberian theorem (for a simple derivation see
Appendix A.2 of [21]), this gives the power-law decay in the time domain
$\displaystyle F_{n}(t\,|\,L_{0})$
$\displaystyle\sim\frac{L_{0}\,\alpha^{1-2^{1-n}}}{-\Gamma(-2^{-n})D^{1-2^{-n}}}\,\frac{1}{t^{1+2^{-n}}}\,,\qquad
t\rightarrow\infty\,.$ (10b)

Thus the long-time tail of the $n^{\text{th}}$-passage probability decays
progressively more slowly as $n$ increases, with the exponent value
approaching $-1$ for $n\to\infty$.

##  3 Number of Encounters with the Boundary

Because the tail of the $n^{\text{th}}$-passage probability becomes fatter as
$n$ increases, the times between encounters also become progressively longer.
Thus we might expect that the total number of encounters will increase only
quite slowly with time. We now show that this naive expectation is what
actually occurs. Let $N(t)$ denote the number of times that the particle
reaches the boundary at time $t$. The probability that there are exactly $n$
encounters at time $t$ is formally given by

$\displaystyle P(N(t)\\!=\\!n\,|\,L_{0})$
$\displaystyle=P(N(t)\\!\geq\\!n\,|\,L_{0})-P(N(t)\\!\geq\\!n+1\,|\,L_{0})\,,$
$\displaystyle=\int_{0}^{t}d\tau F_{n}(\tau\,|\,L_{0})-\int_{0}^{t}d\tau
F_{n+1}(\tau\,|\,L_{0})\,.$ (11)

The average number of encounters $\langle N(t)\rangle$ is given by

$\displaystyle\langle
N(t)\rangle=\sum_{n=0}^{\infty}n\,P(N(t)\\!=\\!n\,|\,L_{0})\,.$ (12a) We
substitute in $P(N(t)\\!=\\!n\,|\,L_{0})$ from Eq. (3), exploit the telescopic
nature of the sum, and also note that the $n=0$ gives no contribution, to
obtain $\displaystyle\langle
N(t)\rangle=\sum_{n=1}^{\infty}P(N(t)\\!\geq\\!n\,|\,L_{0})=\sum_{n=1}^{\infty}\int_{0}^{t}d\tau
F_{n}(\tau\,|\,L_{0})\,.$ (12b)

In the Laplace domain, the above relation becomes

$\displaystyle\langle\widetilde{N}(s)\rangle=\frac{1}{s}\sum_{n=1}^{\infty}\widetilde{F}_{n}(s\,|\,L_{0})\,.$
(13a) We now substitute the expression (6) for the Laplace transform of the
$n^{\text{th}}$-passage probability and find that the Laplace transform of the
average number of encounters is
$\displaystyle\langle\widetilde{N}(s)\rangle=\frac{1}{s}\sum_{n=1}^{\infty}\exp\left[-\epsilon\sum_{m=1}^{n-1}g_{m}(s)-L_{0}\,g_{n}(s)\right]\,,$
(13b) with $g_{n}(s)$ given in (7).

Figure 3: Average number of boundary encounters $\langle N(t)\rangle$ scaled
by $\ln\ln t$ as a function of the inverse of the scaled time for
$D=L=\alpha=1$. The theoretical prediction from (14b) is also shown.

To obtain the long-time asymptotics, we focus on the $s\to 0$ limit of the
above expression:

$\displaystyle\langle\widetilde{N}(s)\rangle\sim\frac{1}{s}\sum_{n=1}^{\infty}\exp\left[-\epsilon\sum_{m=1}^{n-1}\frac{\alpha^{1-2^{1-m}}}{D^{1-2^{-m}}}\,s^{2^{-m}}-L_{0}\frac{\alpha^{1-2^{1-n}}}{D^{1-2^{-n}}}\,s^{2^{-n}}\right]\,.$
(13c)

As shown in A, this limiting behavior of $\langle\widetilde{N}(s)\rangle$
reduces to

$\displaystyle\langle\widetilde{N}(s)\rangle\sim\frac{1}{s\ln
2}\;\ln\left[\ln(\frac{1}{s})\right]\,,$ (14a) which, in the time domain,
gives the long-time behavior $\displaystyle\langle N(t)\rangle\sim\frac{1}{\ln
2}\ln\ln t\approx 1.4427\,\ln\ln t\,.$ (14b)

This dependence agrees well with numerical simulations for the number of
encounters shown in figure 3.

##  4 Location of the Boundary

We now study the time dependence of the location of the boundary. Let $P(L,t)$
denote the spatial location of the boundary at time $t$. This probability
distribution is given by

$\displaystyle P(L,t)$
$\displaystyle=\delta(L-L_{0})\;\text{erf}\left(\frac{L_{0}}{\sqrt{4\pi
Dt}}\right)$
$\displaystyle+\sum_{n=1}^{\infty}\int_{0}^{\infty}\\!\\!d\tau_{1}\ldots
d\tau_{n}\,F_{1}(\tau_{1}\,|\,L_{0})\times\ldots\times
F(\tau_{n}\,|\,\alpha\,\tau_{n-1}\\!+\\!\epsilon)\,\delta(L\\!-\\!L_{0}\\!-\\!n\epsilon\\!-\\!\sum_{m=1}^{n}\alpha\tau_{m})$
$\displaystyle\quad\times\text{erf}\left(\frac{\alpha\tau_{n}+\epsilon}{\sqrt{4\pi
D(t-\sum_{m=1}^{n}\tau_{m})}}\right)\Theta(t-\alpha\sum_{m=1}^{n}\tau_{m})\,.$
(15)

The first term accounts for the case where the diffusing particle never
reaches the boundary. The $n^{\text{th}}$ term in the sum accounts for the
case where the particle reaches the boundary $n$ times. Thus there must be a
first passage, a second passage,…, up to an $n^{\text{th}}$ passage, after
which the particle cannot reach the boundary again. These events are accounted
for by the product of $n$ first-passage probabilities and the trailing error
function. The theta function imposes the condition that the total time must be
larger than the sum of the previous $n$ hitting times. To simplify notation in
the formulas below, we introduce $T_{n}\equiv\sum_{m=1}^{n}\tau_{m}$, the sum
of the first $n$ time intervals between successive encounters.

Computing the average value gives

$\displaystyle\langle L(t)\rangle$
$\displaystyle=L_{0}\,\text{erf}\left(\frac{L_{0}}{\sqrt{4\pi Dt}}\right)$
$\displaystyle+\sum_{n=1}^{\infty}\int_{0}^{\infty}d\tau_{1}\ldots
d\tau_{n}\,F(\tau_{1}\,|\,L_{0})\times\ldots\times
F(\tau_{n}\,|\,\alpha\,\tau_{n-1}\\!+\\!\epsilon)\,(L_{0}\\!+\\!n\epsilon\\!+\\!\alpha
T_{n})$
$\displaystyle\quad\times\text{erf}\left(\frac{\alpha\tau_{n}+\epsilon}{\sqrt{4\pi
D(t-T_{n})}}\right)\Theta(t-T_{n})\,.$ (16)

It is now useful to Laplace transform the above relation. This gives

$\displaystyle\langle\widetilde{L}(s)\rangle$
$\displaystyle=\frac{L_{0}}{s}\,\left(1-e^{-L_{0}\sqrt{\frac{s}{D}}}\right)$
$\displaystyle+\frac{1}{s}\sum_{n=1}^{\infty}\int_{0}^{\infty}d\tau_{1}\ldots
d\tau_{n}\,F(\tau_{1}\,|\,L_{0})\times\ldots\times
F(\tau_{n}\,|\,\alpha\,\tau_{n-1}+\epsilon)\,(L_{0}+n\epsilon+\alpha T_{n})$
$\displaystyle\quad\times\left(1-e^{-(\alpha\tau_{n}+\epsilon)\sqrt{{s}/{D}}}\right)e^{-sT_{n}}\,.$
(17a) We argue that the main contribution to $\langle\widetilde{L}(s)\rangle$
comes from the large-$n$ terms in the sum. These terms will involve values of
$\tau_{n}$ that typically are also large. Thus it is plausible that the
exponential term in the parentheses in the last line is negligible. With this
assumption, we find $\displaystyle\langle\widetilde{L}(s)\rangle$
$\displaystyle\sim\frac{1}{s}\sum_{n=1}^{\infty}\int_{0}^{\infty}\\!\\!d\tau_{1}\ldots
d\tau_{n}\,F(\tau_{1}\,|\,L_{0})\times\ldots\times
F(\tau_{n}\,|\,\alpha\,\tau_{n-1}+\epsilon)\,(L_{0}\\!+\\!n\epsilon\\!+\\!\alpha
T_{n})e^{-sT_{n}}\,,$ (17b)

where we also drop the first term because it is negligible. Furthermore, the
integral of the $n$-fold product of first-passage probabilities is simply
$\widetilde{F}_{n}(s\,|\,L_{0})$. Using this identification, we can write the
average in the simpler form

$\displaystyle\langle\widetilde{L}(s)\rangle$
$\displaystyle\sim\frac{1}{s}\left[\sum_{n=1}^{\infty}\left(L_{0}+n\epsilon-\alpha\,\frac{\partial}{\partial
s}\right)\widetilde{F}_{n}(s\,|\,L_{0})\right]\,.$ (18)

Following similar reasoning as that given in A, the leading-order behavior is
given by the last term in the brackets. Thus

$\displaystyle\langle\widetilde{L}(s)\rangle\sim-\frac{\alpha}{s}\frac{\partial}{\partial
s}\sum_{n=1}^{\infty}\widetilde{F}_{n}(s\,|\,L_{0})$
$\displaystyle\sim-\frac{\alpha}{s\ln 2}\frac{\partial}{\partial
s}\ln\left[\ln\left(\frac{1}{s}\right)\right]\,,$
$\displaystyle\sim\frac{\alpha}{s^{2}\ln 2\ln(1/s)}\,,\qquad s\to 0\,.$ (19a)

Figure 4: Rescaled average position of the boundary $\langle L(t)\rangle$ as a
function of time for $D=L=\alpha=1$.

In the time domain, we then obtain

$\displaystyle\langle L(t)\rangle\sim\frac{\alpha\,t}{\ln 2\ln t}\,,\qquad
t\to\infty\,.$ (19b)

This asymptotic behavior is in good agreement with numerical simulations as
shown in figure 4. The numerical results clearly illustrate that $\langle
L(t)\rangle\propto t/\ln(t)$ for $t\to\infty$. However, the amplitude that is
found numerically is roughly twice the value of the amplitude that is given in
Eq. (19b). We do not know the source of the discrepancy, but it could stem
from the neglect of the exponential term in Eq. (17).

##  5 Concluding Comments

We investigated a simple one-dimensional moving boundary problem that is
driven by the motion of a single Brownian particle. This particle moves freely
on the infinite line and whenever it encounters the boundary, the boundary
instantaneously moves a distance that is proportional to the time between
successive collisions between the particle and the boundary. We determined
some natural observables of this process. The probability that the particle
_first_ hits the boundary for the $n^{\text{th}}$ time asymptotically decays
as $t^{-(1+2^{-n})}$. Thus each successive first-passage event is governed by
a progressively fatter tail. The number of collisions between the particle and
the boundary scales as $\ln\ln t$; this is the same dependence of the iterated
logarithm law of free Brownian motion [16, 17, 18], and perhaps there is some
unifying mechanism that links our moving boundary problem with free diffusion.
In spite of the fact that encounters between the particle and the boundary are
rare, the position $L(t)$ of the boundary moves nearly ballistically:
$L(t)\sim t/\ln t$. This rapid boundary motion indicates that there must be
some long time intervals between successive particle-boundary encounters, so
that the boundary moves by a large distance when such an encounter occurs.

## Acknowledgments

BD acknowledges the financial support of the Luxembourg National Research Fund
(FNR) (App. ID 14548297). SR gratefully acknowledges partial financial support
from NSF Grant DMR-1910736.

##  Appendix A Asymptotic analysis of $\langle\widetilde{N}(s)\rangle$

In this appendix, we study the small $s$ asymptotic behavior of (13c):

$\displaystyle\langle\widetilde{N}(s)\rangle\sim\frac{1}{s}\sum_{n=1}^{\infty}\exp\left[-\epsilon\sum_{m=1}^{n-1}\frac{\alpha^{1-2^{1-m}}}{D^{1-2^{-m}}}\;s^{2^{-m}}-L_{0}\frac{\alpha^{1-2^{1-n}}}{D^{1-2^{-n}}}\;s^{2^{-n}}\right]\,,\quad
s\to 0\,.$ (20)

The sum over $n$ can be split roughly into two parts: (i) one is the
contribution when $n$ runs from $0$ to $n^{*}=n^{*}(s)$ such that
$s^{2^{-n^{*}}}=O(1)$, and (ii) the contribution when $n$ runs from $n^{*}$ to
$\infty$. That is

$\displaystyle\langle\widetilde{N}(s)\rangle\sim\frac{1}{s}\sum_{n=1}^{n^{*}}\exp\left[-L_{0}\frac{\alpha^{1-2^{1-n}}}{D^{1-2^{-n}}}\;s^{2^{-n}}\right]+\frac{1}{s}\sum_{n^{*}}^{\infty}\exp\left[-\epsilon\left(\sum_{m=1}^{n-1}\frac{\alpha^{1-2^{1-m}}}{D^{1-2^{-m}}}\right)-L_{0}\frac{\alpha^{1-2^{1-n}}}{D^{1-2^{-n}}}\right]\,,\quad
s\to 0\,.$ (21)

Because the series in the second term converges, we are left with

$\displaystyle\langle\widetilde{N}(s)\rangle\sim\frac{1}{s}\sum_{n=1}^{n^{*}}\exp\left[-L_{0}\frac{\alpha^{1-2^{1-n}}}{D^{1-2^{-n}}}\,s^{2^{-n}}\right]\,,\qquad
s\to 0\,.$ (22)

Because the second term is negligible, the final result is independent of the
cutoff $\epsilon$. The terms for $n<n^{*}$ will tend to $1$, and therefore we
find

$\displaystyle\langle\widetilde{N}(s)\rangle\sim\frac{1}{s}\,n^{*}\,,\quad
s\to 0\,.$ (23)

Finally, using that $s^{2^{-n^{*}}}=O(1)$, we obtain (14a).

## References

  * [1] Crank J and Crank J 1984 Free and moving boundary problems (Oxford University Press, USA)
  * [2] Rubinstein L 2000 The Stefan Problem vol 8 (American Mathematical Society)
  * [3] Langer J S 1980 Rev. Mod. Phys. 52(1) 1–28 URL https://link.aps.org/doi/10.1103/RevModPhys.52.1
  * [4] De Bruyne B, Randon-Furling J and Redner S 2021 Journal of Statistical Mechanics: Theory and Experiment 2021 013203
  * [5] Evans M R and Majumdar S N 2011 Phys. Rev. Lett. 106 160601
  * [6] Evans M R and Majumdar S N 2011 J. Phys. A: Mathematical and Theoretical 44 435001
  * [7] Evans M R, Majumdar S N and Schehr G 2020 J. Phys. A: Mathematical and Theoretical
  * [8] Boyer D and Solis-Salas C 2014 Phys. Rev. Lett. 112(24) 240601
  * [9] Christou C and Schadschneider A 2015 J. Phys. A: Mathematical and Theoretical 48 285003
  * [10] Rotbart T, Reuveni S and Urbakh M 2015 Phys. Rev. E 92(6) 060101
  * [11] Majumdar S N, Sabhapandit S and Schehr G 2015 Phys. Rev. E 92(5) 052126
  * [12] Reuveni S 2016 Phys. Rev. Lett. 116 170601
  * [13] Pal A and Reuveni S 2017 Phys. Rev. Lett. 118 030603
  * [14] Belan S 2018 Phys. Rev. Lett. 120 080601
  * [15] Bodrova A S, Chechkin A V and Sokolov I M 2019 Phys. Rev. E 100 012119
  * [16] Khintchine A 1924 Math 32 203–219
  * [17] Feller W 2008 An Introduction to Probability Theory and its Applications (John Wiley & Sons)
  * [18] Mörters P and Peres Y 2010 Brownian motion vol 30 (Cambridge University Press)
  * [19] Redner S 2001 A Guide to First-Passage Processes (Cambridge University Press)
  * [20] Bray A J, Majumdar S N and Schehr G 2013 Advances in Physics 62 225–361
  * [21] Evans M, Majumdar S N and Zia R 2006 Journal of Statistical Physics 123 357–390