what k should be to optimize total averaged cost across time, and in particular if that k is the same as kLB, the k that LB uses.

Now as we go from one time step to the next, the routing decision made W time steps ago drops out of the computation of S ( t ), while the routing decision just made is newly included. In general, S(t + 1) = S(t) + 1 if the router just used A at time t and used link B at the time W time steps into the past. On the other hand, S(t + 1) = S(t) = 1 if the router just used B and used A W time steps ago, while S ( t + 1) = S ( t ) if the routing decision just made is the same as the routing decision W time steps ago. So in general, S ( t ) can only change by -1, 0, or +1 as we go from one time step to the next.

Consider cases where 1 < k < W - 1, so that eventually the router must choose an A,
and at some subsequent time t* the router switches from A to B . At that time s( t* - 1) = A
and s(t*) = B. This implies that S(t* - 1) ≤ k, S(t*) > k. Define the value S(t* - 1) as k*.

Note that S(t*) = k* + 1, and k = 1 < k* < k.

Now for any time t ′ , if S(t ′ ) = k ∗ + 1, s(t ′ + 1) = B ′ and the only possible next values are S(t' + 1) = k* or S(t' + 1) = k* + 1, depending on the old decision s(t - W) that gets dropped out of the window. Similarly, if S ( t ′ ) = k *, s ( t ′ + 1) = A, and the only possible next values are S ( t ′ + 1) = k * or S ( t ′ + 1) = k * + 1, again depending on the old decision being dropped. So we see that once S(t') E {k*, k* + 1}, it stays there forever.

This means that because of the relationship between k and k*, in any interval of W
consecutive time steps subsequent to t*, the number of packets sent along A by router X
must be E (k - 1, k + 1]. (Note that it is possible to send k + 1 packets along A, but not k - 1 packets.  Therefore the number sent along B must be ∈ [ W − ( k + 1), W − ( k − 1)).  Each time that a packet is sent along A the cost incurred is the cost of link A with average traffic level S(t)/W, CA(S(t)/W). Similarly, each time the link B is chosen, the cost incurred is C B (1 − S ( t )/W ), Since S ( t ) ∈ { k *, k * + 1 }, and both C A ( . ) and C B ( . ) are monotonically increasing, the cost for sending the packet down link A E ( CA (( k - 1)/W), CA (( k + 1)/W],
and that for sending it down link B is contained in [ C B (1 - ( k +1)/W), C B (1 - ( k - 1)/W)).

Now we know that the choice of A must have average frequency (across all time) between k*/W and (k* + 1)/W. Similarly, B will have average frequency between (1 - (k* + 1)/W)
and 1 - k */W. Accordingly, the average cost is bounded above by

$$\frac{k^{*}+1}{W}C_{A}\left(\frac{k+1}{W}\right)\ \ +\ \ \left(1-\frac{k^{*}}{W}\right)C_{B}\left(1-\frac{k-1}{W}\right)\,\tag{5}$$

where the first term provides the maximum possible average cost for using link A, while the second term independently provides the maximum possible average cost for using link B. Note that the actual cost will be lower since the two frequencies in this bound, one for A and one for B , cannot both have the values indicated. Because k - 1 < k * ≤ k and since 1 - kyl = 1 + kyl - kyl, our upper bound is itself bounded above by

$$\frac{k+1}{W}C_{A}\left(\frac{k+1}{W}\right)\ \ +\ \ \left(1+\frac{2}{W}-\frac{k+1}{W}\right)C_{B}\left(1+\frac{2}{W}-\frac{k+1}{W}\right)\;.\tag{6}$$

The optimal k will result in an average cost lower than the minimum over all k of the upper bound on average cost, given in Equation 6. So the average cost for the optimal k is bounded above by the minimum over k of this upper bound. Lable this argmin of Equation 6 k'.