1 Introduction

The online buffer management problem proposed by Aiello et al. [1] formulates the management of buffers to store arriving packets in a network switch with Quality of Service (QoS) support as an online problem. This problem has received much attention among online problems and has been studied for the last fifteen years, which leads to developing various variants of this problem (see comprehensive surveys [17, 26]). Kesselman et al. [23] proposed the bounded delay buffer management problem as one of the variants, whose definition is as follows: Packets arrive to a buffer over time. A packet p is specified by the release time r(p), value v(p) and deadline d(p). An algorithm is allowed to transfer at most one packet at each integer time. If the algorithm transmits a packet between its release time and deadline, it can gain its value as the profit. The objective of this problem is to maximize the gained profit. The performance of an online algorithm for this problem is evaluated using competitive analysis [11, 27]. If for any problem instance, the profit of an optimal offline algorithm OPT is at most c times that of an online algorithm A, then we say that the competitive ratio of A is at most c. We call a problem instance the s-bounded instance (or s-bounded delay buffer management problem) in which for any packet p, \(d(p) - r(p) + 1 \le s\). For any \(s \ge 2\), Hajek [19] showed that the competitive ratio of any deterministic algorithm is at least \((1 + \sqrt{5})/2 \ge 1.618\). Very recently, Veselý et al. [28] designed an online algorithm matching the lower bound.

There is much research among online problems to reduce the competitive ratio of an online algorithm for the original problems by adding extra abilities to the algorithm. One of the major methods is called the lookahead ability, with which an online algorithm can obtain information about arriving packets in the near future. This ability is introduced to various online problems: the bin packing problem [18], the paging problem [2, 12], the list update problem [3], the scheduling problem [25] and so on. Then, Böhm et al. [9, 10] introduced the lookahead ability to the bounded delay buffer management problem, that is, they gave an online algorithm for this problem an ability to obtain the information about future arriving packets and analyzed its performance.

Previous Results and Our Results. Böhm et al. [9, 10] studied the 2-bounded bounded delay buffer management problem with lookahead. They designed a deterministic algorithm whose competitive ratio is at most \(( - 1 + \sqrt{13})/2 \le 1.303\). Also, they proved that the competitive ratio of any deterministic algorithm is at least \(( 1 + \sqrt{17})/4 \ge 1.280\).

In this paper, we show an online algorithm matching their lower bound for this problem, that is, its competitive ratio is exactly \((1 + \sqrt{17})/4\). Since the original bounded delay buffer management problem has been solved completely by Veselý et al. [28] just recently, the bounded delay buffer management problem with lookahead is one of the most important variants which should be solved among several variants of this problem. Our result will help to develop an optimal algorithm for s-bounded instances.

Related Results. In the full version [10] of the paper [9], Böhm et al. studied lower bounds on the competitive ratios of online algorithms with more generalized lookahead. Specifically, the lookahead ability in [9] at a time t enables an online algorithm to obtain the information about packets p such that \(r(p) = t+1\). In [10], for a positive integer \(\ell \), they considered the case where the ability at a time t enables an online algorithm to obtain the information about packets p such that \(r(p) \le t+\ell \). They showed that a lower bound of any deterministic algorithm is \(\frac{1+\sqrt{5 + 8 \ell + 4 \ell ^2}}{2\ell + 2}\). Moreover, they proved that for any \(\ell \ge 1\), a lower bound of any randomized online algorithm is 1.25.

As mentioned above, for the s-bounded delay model without lookahead, Hajek [19] showed that the competitive ratio of any deterministic algorithm is at least \((1 + \sqrt{5})/2 \ge 1.618\) in the case of \(s \ge 2\). Independently, this bound was also shown in [4, 13, 29]. Several deterministic algorithms have been developed [5, 9, 10, 14, 16, 23] and very recently, Veselý et al. [28] designed an optimal online algorithm. Moreover, in the case where an algorithm must decide which packet to transmit on the basis of the current buffer situation, called the memoryless case, some results were shown [5, 14, 16]. The agreeable deadline variant has also been studied. In this variant, the larger the release times of packets are, the larger their deadlines are. Specifically, for any packets p and \(p'\), \(d(p) \le d(p')\) if \(r(p) < r(p')\). The lower bound of \((1 + \sqrt{5})/2\) by Hajek [19] is applicable to this variant. Li et al. [21, 24] displayed an optimal algorithm, whose competitive ratio matches the lower bound. The case in which for any packet p, \(d(p) - r(p) + 1 = s\) has also been studied, called the s-uniform delay variant, which is a specialized variant of the agreeable deadline variant. The current best upper bound for this variant is \((1 + \sqrt{5})/2\) [21, 24]. Also, in the case of \(s = 2\), Chrobak et al. [15] designed an optimal online algorithm whose competitive ratio is 1.377 [15].

The research on randomized algorithms for the bounded delay buffer management problem has also been conducted extensively [5, 6, 13, 14, 20,21,22]. In the case in which s is general, the current best upper and lower bounds are \(e/(e-1) \le 1.582\) [5, 14, 22] and \(5/4 = 1.25\) [13], respectively, against an oblivious adversary were shown. Upper and lower bounds of \(e/(e-1)\) [6, 22] and \(4/3 \ge 1.333\) [6], respectively, against an adaptive adversary were shown. For any fixed s, lower bounds are the same with the bounds in the case in which s is general while upper bounds are \(1/(1 - (1 - \frac{1}{s})^s)\) [22] against the both adversaries.

A generalization of the bounded delay buffer management problem has been studied, called the weighted item collection problem [7, 8, 22]. In this problem, an online algorithm does not know the deadline of each packet but knows the relative order of the deadlines of packets. Many other variants of the buffer management problem have been studied extensively (see e.g. [17, 26]).

2 Model Description

We formally give the definition of the 2-bounded delay buffer management problem with lookahead, which is addressed in this paper. An input of this problem is a sequence of phases. Time begins with zero and a phase occurs at an integer time. Each phase consists of three subphases. The first occurring subphase is the arrival subphase. At an arrival subphase, arbitrarily many packets can arrive to a buffer. The buffer has no capacity limit and hence, all arriving packets can always be accepted to the buffer. A packet p is characterized by the release time, deadline and value, denoted by r(p), d(p) and v(p) respectively. Arrival times and deadlines are non-negative integers and values are positive reals. \(d(p) - r(p) \le 1\) holds because we focus on 2-bounded instances. The second subphase is the transmission subphase. At a transmission subphase, an algorithm can transmit at most one packet from its buffer if any packet. At the transmission subphase at a time t, the algorithm can obtain the information about packets arriving at time \(t+1\) using the lookahead ability. The third subphase is the expiration subphase. At an expiration subphase, a packet which has reached its deadline is discarded from its buffer. That is, at the expiration subphase at a time t, all the packets p in the buffer such that \(d(p) = t\) are discarded.

The profit of an algorithm is the sum of the values of packets transmitted by the algorithm. The objective of this problem is to maximize the gained profit. Let \(V_{A}(\sigma )\) denote the profit of an algorithm A for an input \(\sigma \). Let OPT be an optimal offline algorithm. We say that the competitive ratio of an online algorithm ON is at most c if for any input \(\sigma \), \(V_{OPT}(\sigma ) \le V_{ON}(\sigma ) c\).

3 Matching Upper Bound

3.1 Notation and Definitions

We give definitions before defining our algorithm CompareWithPartialOPT (CP). For any integer time t and any algorithm A, \(B_{A}(t)\) denotes the set of packets in A’s buffer immediately before the arrival subphase at time t. That is, each packet p in the set is not transmitted before t such that \(t > r(p)\) and \(t \le d(p)\). Let us define an offline algorithm PO, which stands for a Partial OPT, which stores all the packets in the buffer of CP at a time and woks optimally given a subinput from the time. For integer times \(t, t' \ge t\) and \(t'' \in \{ t', t'+1 \}\) and an input \(\sigma \), let \({PO}(t, t', t'')\) be an offline algorithm such that the set of packets in \({PO}(t, t', t'')\)’s buffer immediately before the arrival subphase at time t is equal to that of \(B_{CP}(t)\)’s, and if the subinput of \(\sigma \) during time \([t, t']\) is given to \({PO}(t, t', t'')\), that is, packets p such that \(r(p) \in [t, t']\) arrive to \({PO}(t, t', t'')\)’s buffer during time \([t, t']\), then \({PO}(t, t', t'')\) is allowed to transmit \(t'' - t + 1\) packets only from time t to \(t''\) inclusive, that is, at \(t'' - t + 1\) transmission subphases, and chooses the packets whose total profit is maximized. If there exist packets with the same value in \({PO}(t, t', t'')\)’s buffer, \({PO}(t, t', t'')\) follows a fixed tie breaking rule. Also, \(P(t, t', t'')\) denotes the set of \(t'' - t + 1\) packets transmitted by \({PO}(t, t', t'')\) during time \([t, t'']\). Note that for any t and \(t' \ge t\), the following relations hold because of the optimality of packets transmitted by \({PO}(t, t', t'')\) during time \([t, t'']\):

$$\begin{aligned} P(t, t', t')&\subseteq P(t, t'+1, t'+1) \end{aligned}$$
(1)
$$\begin{aligned} P(t, t', t')&\subseteq P(t, t', t'+1) \end{aligned}$$
(2)

and

$$\begin{aligned} P(t+1, t', t') \subseteq P(t, t', t'). \end{aligned}$$
(3)

We define for any t and \(i \ge 0\),

$$\begin{aligned} \{ m_{i}(t) \} = P(t, t+i, t+i) \backslash P(t, t+i-1, t+i-1) \end{aligned}$$

and any \(i \ge 1\),

$$\begin{aligned} \{ q_{i}(t) \} = P(t, t+i, t+i+1) \backslash P(t, t+i, t+i). \end{aligned}$$

Also, we define

$$\begin{aligned} P(t, t-1, t-1) = \varnothing . \end{aligned}$$

If \(m_{i}(t)\) (\(q_{i}(t)\)) does not exist, that is, the above equality is the empty set, then we assume that a packet whose value is 0 is given. This assumption is used to make the description of CP simpler and does not affect the performance of CP. Moreover, if there exists a packet p such that both \(v(p) = v(q_{1}(t))\) holds and either \(r(p) = t\) or \(p \in B_{CP}(t)\), that is, CP can transmit p at t, then \({q}_{0}(t)\) denotes p. Also, we define \( m_{01}(t) \in \arg \max \{ m_{0}(t), m_{1}(t) \}. \) Let \(V(t, t', t'')\) denote the total value of packets in \(P(t, t', t'')\). That is, \(V(t, t', t'') = \sum _{ p \in P(t, t', t'')} v(p)\). We describe each value in the algorithm definition for ease of presentation as follows: \( m_{i} = m_{i}(t), \) \( m_{01} = m_{01}(t), \) \( q_{i} = q_{i}(t) \) and, \( R = (1 + \sqrt{17})/4. \)

3.2 Idea Behind Algorithm Design

In this section, we explain the idea behind designing our algorithm CP for better understanding. Suppose that CP decides which packet to transmit at a time t. Let us assume that at t, the buffer of CP stores all the packets in the buffer of OPT at t. We guarantee that this assumption holds at a time satisfying some conditions in a lemma of the full version of this paper. Due to page limitations, we omit all of the proofs in this paper. The full version of this paper is available at https://arxiv.org/abs/1807.00121. If this assumption holds, CP is able to detect two packets OPT transmits at times t and \(t+1\). To detect here means that CP calculates which packets OPT transmits at these times cause the worst situation with respect to the profit ratio. Let V be the maximum total value of two packets which OPT transmits at t and \(t+1\). CP chooses packets p and \(p'\) at t and \(t+1\), respectively, from packets which are revealed to CP at t such that \(V \le R(v(p) + v(p'))\) holds. Note that \(p'\) may arrive at \(t+1\). Although both CP’s and OPT’s buffers have the same packets at some time, the optimal choice depends on the instance, which in turn depends on CP’s choice and thus CP might make a non-optimal choice in general. and hence, CP does not always transmit the packets as the ones which OPT transmits although they have the same packets at t. If CP could choose packets for each \(t = 0, 2, 4, \ldots \) to satisfy the above inequality, we could prove that the competitive ratio of CP is at most R. However, this is impossible. For example, suppose that packets \(p_{0}, p_{1}\) and \(p_{2}\) are given at time 0 such that \(d(p_{0}) = 0\), \(d(p_{1}) = 1\) and \(d(p_{2}) = 2\) and no other packets are given further. Also, suppose that CP transmits \(p_{1}\) and \(p_{2}\) at times 0 and 1, respectively and OPT transmits \(p_{0}, p_{1}\) and \(p_{2}\) at times 0, 1 and 2, respectively. In this case, CP does not transmit any packet at time 2 and thus, we cannot prove the above inequality.

Thus, the length of a time interval which CP uses to evaluate its competitive ratio is not fixed (such as 2 mentioned above) but variable as follows. Let us assume again that at a time t, the buffer of CP stores all the packets in the buffer of OPT at t. Also, suppose that CP decides which packet to transmit at a time \(t'(\ge t)\) (the fact that \(t' \le t+2\) holds will be shown later by the definition of CP). By this assumption, CP can detect \(t'-t+2\) packets transmitted by OPT during the time \([t, t'+1]\) (in some special cases, CP can detect \(t'-t+3\) packets transmitted by OPT during \([t, t'+2]\)). Let \(V'\) be the maximum total value of packets which OPT transmits during this time interval. CP chooses packets p and \(p'\) at \(t'\) and \(t'+1\), respectively, considering the total value U of packets which CP already transmitted during time \([t, t'-1]\) such that \(V' \le R(U + v(p) + v(p'))\) holds. For example, suppose that packets \(q_{0}(0),m_{0}(0)\) and \(m_{1}(0)\) are given at time 0 whose values satisfy the execution conditions of Case 1.2.3.1 in CP. If CP transmits \(m_{0}(0)\) and \(m_{1}(0)\) at times 0 and 1, respectively, then CP can detect that OPT transmits \(q_{0}(0),m_{0}(0)\) and \(m_{1}(0)\) at times 0, 1 and 2, respectively. In this case, \(t = t'=0\) holds, and the above inequality holds by the condition of Case 1.2.3.1.

The sequences of packets which OPT transmits during \([t, t'+1]\) (or \([t, t'+2]\)) are classified into three categories according to a packet \(p'\) which CP transmits at \(t'+1\) (this fact will be proved in some lemmas of the full version of this paper): (a) Packets which are given during \([t, t'+1]\) satisfy some conditions and OPT transmits specific packets whose total value is \(V(t, t'+1, t'+1)\). (b) If the deadline of \(p'\) is \(t'+1\), then the total value of packets which OPT transmits during \([t, t'+1]\) is at most \(V(t, t'+1, t'+1)\). (c) If the deadline of \(p'\) is \(t'+2\), then the total value of packets which OPT transmits during \([t, t'+2]\) is at most \(V(t, t'+1, t'+2)\). Please refer to Table 1. ‘Case’ column shows the names of cases executed by CP at t. ‘Type’ column shows the categories of packet sequences transmitted by OPT during \([t, t'+1]\) (or \([t, t'+2]\)). ‘t’ and ‘\(t+1\)’ in ‘CP’ column show packets which CP transmits at t and \(t+1\), respectively. Similarly, ‘t’, ‘\(t+1\)’ and ‘\(t+2\)’ in ‘OPT’ column show packets which CP detects at time t that OPT transmits at t, \(t+1\) and \(t+2\), respectively. ‘Value’ column shows the total value of the packets detected by CP. For example, packets detected at Case 1.2.3.1 are classified into (c). CP transmits \(m_{0}(t)\) and \(m_{1}(t)\) at times 0 and 1, respectively. CP can detect that OPT transmits \(q_{0}(t)(=q_{1}(t)),m_{0}(t)\) and \(m_{1}(t)\) at times 0, 1, and 2, respectively, and the total value of these packets is \(V(t, t+1, t+2)\). On the other hand, suppose that packets satisfying the condition of Case 1.2.3.2 are given. In this case, at time t, if CP decides which packet to transmit at \(t+1\), then a situation in which the above inequality does not hold can occur whichever packet which arrives at or before \(t+1\) CP chooses. Note that if this condition is satisfied, then this situation occurs not only for CP but also any online algorithm, which causes the definition of CP lengthy. Hence, CP chooses \(q_{0}(t)\) as a packet for the transmission subphase at t, and decides which packet to transmit for the transmission subphase of time \(t+2\) after making sure of packets at \(t+1\) with lookahead. That is, CP executes Step 2 at the transmission subphase at \(t+1\) to choose packets which CP transmits at \(t+1\) and \(t+2\).

Similarly to the case at time t, CP chooses packets at \(t+1\) considering the value \(U = v(q_{0}(t))\) of the packet \(q_{0}(t)\) which CP transmitted at t so that the above inequality holds. Please refer to the row of Case 2.2.1 in Table 2, which is described in the same manner as the previous one. Suppose that packets are given satisfying the conditions of Case 2.2.1. If CP transmits \(m_{01}(t)\) and \(m_{2}(t)\) at times \(t+1\) and \(t+2\), respectively, then CP can detect that OPT transmits \(m_{0}(t), m_{1}(t)\) and \(m_{2}(t)\) at times t, \(t+1\) and \(t+2\), respectively. These packets are classified into (b) and the above inequality holds because of the condition of Case 2.2.1. Unfortunately, suppose that packets satisfying the condition of Case 2.2.2.3 are given. In this case, at \(t+1\), if CP decides which packet to transmit at \(t+2\), then a situation in which the above inequality does not hold can also occur. Note that if the conditions of Cases 1.2.3.2 and 2.2.2.3 are satisfied at times t and \(t+1\), respectively, then this situation occurs for any online algorithm. Thus, CP chooses \(m_{0}(t)\) as a packet for \(t+1\), and executes Step 3 at \(t+2\) to choose packets which CP transmits at \(t+2\) and \(t+3\). Fortunately, as Table 3 shows, at time \(t+2\), if CP chooses packets to transmit at \(t+2\) and \(t+3\) appropriately, then the above inequality holds at any of Cases 3.1 - 3.2.3. Moreover, we will prove that the buffer of CP stores all the packets in the buffer of OPT at \(t'+2\) in a lemma of the full version (there exists some exception for a packet sequence classified into (c)). Hence, in the next step, we can regard time \(t'+2\) as a new base time, which was time t in the above discussion, and evaluate the profit ratio for each time interval recursively. In this way, CP is designed so that at each time interval \([t, t'+1]\) (or \([t, t'+2]\)), the corresponding profit ratio is at most R, that is, its competitive ratio is at most R.

Table 1. Packet prediction at Step 1 at time t
Full size table
Table 2. Packet prediction at Step 2 at time \(t + 1\)
Full size table
Table 3. Packet prediction at Step 3 at time \(t + 2\)
Full size table

3.3 Algorithm

The executions of CP are divided into stages. Each stage consists of a single transmission subphase, two consecutive transmission subphases, three consecutive transmission subphases or four consecutive transmission subphases.

CP uses the internal variable \(s_{t}\) for holding the name of a packet which CP transmits at a time t. \(s_{t'} = {\texttt {null}}\) holds at first for any integer \(t'\). CP uses the constant tmp1 (tmp2) if at time t (\(t+1\)), CP cannot decide which packet to transmit at \(t+1\) (\(t+2\)) in Case 1.2.3.2 (2.2.2.3). On the other hand, once the name of a packet is set to \(s_{t+1}\) at time t, CP certainly transmits the packet at \(t+1\). It is applied to \(s_{t+2}\) (\(s_{t+3}\)) which is set at \(t+1\) (\(t+2\)).

figure a

3.4 Overview of the Analysis

For ease of analysis, we assume that if CP does not store any packet in its buffer at the transmission subphase at a time t, no packets arrive at or after time \(t+1\) any more, that is, the input is over. Note that CP stores no packets but OPT may store one at t, that is, transmit it then. Since we consider a 2-bounded instance, the buffers of OPT and CP are both empty after the expiration subphase at t. This situation is equal to the one before the first packet arrives at time 0 and by the definition of CP, we regard a time at which the buffers are empty as time 0. Therefore, this assumption does not affect the performance of CP.

Consider a given input \(\sigma \). Let k denote the number of stages after \(\sigma \) is over. Let \(\tau \) be the last time at which CP transmits a packet. We partition the time sequence \([0, \tau ]\) into k sequences \(T_{i}\ (i = 1, \ldots , k)\) disjointly such that \(T_{i}\) consists of times at which the executions of the ith stage are done. Specifically, if \(T_{i} = [t_{i}, t'_{i}]\), then \(t_{i} \le t'_{i}\), \(t_{1} = 0\), \(t'_{k} = \tau \) and for any \(j = 2, \ldots , k\), \(t_{j} = t'_{j-1} + 1\). The size of each \(T_{i}\) depends on times at which CP does the executions of the ith stage, that is, which case CP executes at each time: Suppose that \(T_{i} =[t, t']\), in which t and \(t'\) are integer times.

  • If Case 1.1 is executed at t, then \(t' = t\).

  • If Case 1.2.1, 1.2.2 or 1.2.3.1 is executed at t, then \(t'=t+1\).

  • If Case 1.2.3.2 is executed at t and Case 2.1, 2.2.1 or 2.2.2.2 at \(t+1\), then \(t' = t+2\).

  • If Cases 1.2.3.2 and 2.2.2.1 are executed at t and \(t+1\), respectively, then \(t' = t+1\).

  • If Cases 1.2.3.2 and 2.2.2.3 are executed at t and \(t+1\), respectively, and Case 3.1, 3.2.1 or 3.2.3 is executed at \(t+2\), then \(t' = t+3\).

  • If Cases 1.2.3.2 and 2.2.2.3 are executed at t and \(t+1\), respectively, and Case 3.2.2 is executed at \(t+2\), then \(t' = t+2\).

For a time t, a packet whose release time is t and deadline is \(t+1\) is called a \(2_{t}\)-packet. If for a time t, CP transmits a \(2_{t}\)-packet p at t and OPT transmits p at \(t+1\), then we call the time \(t+1\) an extra time (\(e\text {-}time\), for short). On the other hand, for each \(i = 1, \ldots , k\), let us define \(T'_{i}\), which is formally defined later, each of which is a subsequence of the time sequence \([0, \tau ']\), in which \(\tau '\) is the last time at which OPT transmits a packet. They are not always disjoint differently from \(T_{i}\). To analyze the performance of CP, for each \(i \in [1, k]\), we will compare the total value of packets transmitted by CP during the time \(T_{i}\) with that by OPT during the time \(T'_{i}\). \(T'_{i}\) is defined as follows: For \(T_{i} = [t, t']\) in which t and \(t'(\ge t)\) are integer times, we define \(T'_{i} = [t, \hat{t}']\), in which if \(t'+1\) is an e-time, then \(\hat{t}' = t'+1\). Otherwise, \(\hat{t}' = t'\). We give the lemma about \(T'_{i}\).

Lemma 1

A time in \([0, \tau ']\) is contained in some \(T'_{i}\).

For any i, we define an offline algorithm \(OPT_{i}\) to bound the value of packets transmitted by OPT during time \(T'_{i} = [t, t']\), in which t and \(t'(\ge t)\) are integer times. Roughly speaking, if t is not an e-time, then \(OPT_{i}\) transmits the same packet as a packet OPT transmits during \(T'_{i}\). If t is an e-time, then \(OPT_{i}\) transmits the same packet as a packet OPT transmits during \(T'_{i}\) except for t. However, \(OPT_{i-1}\) transmits the same packet as OPT at t.

First, let us define packets in the buffer of \(OPT_{i}\) for \(T_{i} =[t, t']\). If \(t = 1\), \(B_{OPT_{i}}(t) = B_{OPT}(t)\). If \(t \ge 2\) and t is not an e-time, then \(B_{OPT_{i}}(t) = B_{OPT}(t)\). If \(t \ge 2\) and t is an e-time, then \(B_{OPT_{i}}(t) = B_{OPT}(t) \backslash \{ p \}\), in which p is the \(2_{t-1}\)-packet which OPT transmits at t. Then, for \(T_{i} = [t, t']\) and \(T'_{i} =[t, \hat{t}']\), we define \(OPT_{i}\) as follows: The subinput of \(\sigma \) during time \(T'_{i}\) is given to \(OPT_{i}\), that is, packets p such that \(r(p) \in T'_{i}\) arrive to \(OPT_{i}\)’s buffer during time \(T'_{i}\) according to their release times. Then, \(OPT_{i}\) is allowed to transmit \(\hat{t}'-t+1\) packets only from time t to \(\hat{t}'\) inclusive, that is, at \(\hat{t}'-t+1\) transmission subphases, and chooses the packets whose total profit is maximized. If there exist packets with the same value in \(OPT_{i}\)’s buffer, \(OPT_{i}\) follows the same tie breaking rule as OPT.

We use \({PO}(t, t', \hat{t}')\) to define CP and can evaluate the profit of CP using the profit of \({PO}(t, t', \hat{t}')\) during \(T_{i}\). On the other hand, we bound the profit of OPT using that of \(OPT_{i}\) during \(T'_{i}\). Then, we evaluate the relations between the profit of \({PO}(t, t', \hat{t}')\) and that of \(OPT_{i}\). For any \(i \in [1, k]\), let \(V_{i}\) denote the total value of packets transmitted by CP during \(T_{i}\). By definition, \( V_{{CP}}(\sigma ) = \sum _{i = 1}^{k} V_{i}. \) On the other hand, Lemma 1 indicates that a packet which OPT transmits is transmitted at a time in some \(T'_{i'}\) by either \(OPT_{i'}\) or \(OPT_{i'-1}\). Also, by the definition of \(OPT_{i}\), if t is not an e-time, \(OPT_{i}\) transmits a packet at t whose value is at least that transmitted by OPT. If t is an e-time, then \(OPT_{i-1}\) transmits a packet at t whose value is at least that transmitted by OPT and \(OPT_{i}\) may also transmit a packet. That is, the total value of packets transmitted by \(OPT_{i}\) over all \(i \in [1, k]\) is at least that of OPT. For any \(i \in [1, k]\), let \(V'_{i}\) denote the total value of packets transmitted by \(OPT_{i}\) during \(T'_{i}\). Hence, \(V_{OPT}(\sigma ) \le \sum _{i = 1}^{k} V'_{i}\). Since

$$\begin{aligned} \frac{ V_{OPT}(\sigma ) }{ V_{{CP}}(\sigma ) } \le \frac{\sum _{i=1}^{k} V'_{i} }{ \sum _{i = 1}^{k} V_{i} } \le \max _{ i \in [1, k] } \left\{ \frac{ V'_{i} }{ V_{i} } \right\} \!, \end{aligned}$$

we will prove the following lemma:

Lemma 2

For any \(i \in [1, k]\), \(V'_{i} / V_{i} \le (1 + \sqrt{17})/4\).

Therefore, we have the following theorem:

Theorem 1

The competitive ratio of CP is at most \((1 + \sqrt{17})/4\).