zenduck.me: Exponentially Weighted Moving Average

September 3, 2023Agustus 11, 2023 falma.u99 average, exponentially, moving, weighted, zenduckme

Untung99 menawarkan beragam permainan yang menarik, termasuk slot online, poker, roulette, blackjack, dan taruhan olahraga langsung. Dengan koleksi permainan yang lengkap dan terus diperbarui, pemain memiliki banyak pilihan untuk menjaga kegembiraan mereka. Selain itu, Untung99 juga menyediakan bonus dan promosi menarik yang meningkatkan peluang kemenangan dan memberikan nilai tambah kepada pemain.

Berikut adalah artikel atau berita tentang Harian zenduck.me dengan judul zenduck.me: Exponentially Weighted Moving Average yang telah tayang di zenduck.me terimakasih telah menyimak. Bila ada masukan atau komplain mengenai artikel berikut silahkan hubungi email kami di [email protected], Terimakasih.

9.2 Machine Learning and Congestion Control: Project Remy

In this section, we describe the work carried out by Winstein et al. at MIT in which they did a fundamental rethink on how to solve the congestion control problem, based on which they came up with an algorithm called Remy that is radically different from all existing work in this area [1–4]. This algorithm is based on applying ideas from partially observable Markov decision processes (POMDPs) to the congestion control problem.

The basic idea behind the derivation of this algorithm is something that we discovered in Chapter 3, that is, the congestion control problem can be regarded as the solution to the distributed optimization of a network wide utility function (see Section 3.2 and Appendix 3.E in Chapter 3Section 3.2Appendix 3.EChapter 3). By using POMDP/ML techniques, the algorithm learns the best possible congestion control action, in the sense of minimizing this utility function, based on its observations of the partial network state at each source.

The system uses a simple ON-OFF model for the traffic generation process at each source. The sender is OFF for a duration that is drawn from an exponential distribution. Then it switches to the ON state, where it generates a certain number of bytes that are drawn from an empirical distribution of flow sizes or a closed form distribution.

The important ingredients that go into the algorithm include:

•: The form of the utility function that is being minimized
•: The observations of the network state at each source
•: The control action that the algorithm takes based on these observations

We describe each of these in turn:

1.

Utility function: Define the functionthen the form of the network utility function for a connection that Remy uses is given by

(2)

U_{α β δ} (r, T_{s}) = U_{α} (r) - δ U_{β} (T_{s})

Given a network trace, r is estimated as the average throughput for the connection (total number of bytes sent divided by the total time that the connection was “ON”), and T_s is estimated as the average round-trip delay. Note that the parameters

α

and

β

express the fairness vs efficiency tradeoffs for the throughput and delay, respectively (see Appendix 3.E in Chapter 3), and

δ

expresses the relative importance of delay versus throughput. By varying the parameter

δ

, equation 2 enables us to explicitly control the trade-off between throughput and delay for the algorithm. The reader may recall from the section on Controlled Delay (CoDel) in Chapter 4 that legacy protocols such as Reno or Cubic try to maximize the throughput without worrying about the end-to-end latency. To realize the throughput–delay tradeoff, legacy protocols have to use an AQM such as Random Early Detection (RED) or CoDel, which sacrifice some the throughput to achieve a lower delay. Remy, on the other hand, with the help of the utility function in equation 2, is able to attain this trade-off without making use of an in-network AQM scheme.

2.

Network state observations: Remy tracks the following features of the network history, which are updated every time it receives an ACK:

a.: ack_ewma: This is an exponentially weighted moving average of the inter-arrival time between new ACKs received, where each new sample contributes 1/8 of the weight of the moving average.
b.: send_ewma: This is an exponentially weighted moving average of the time between TCP sender timestamps reflected in those ACKs, with the same weight 1/8 for new samples.
c.: rtt_ratio: This is the ratio between the most recent Round Trip Latency (RTT) and the minimum RTT seen during the current connection.

Winstein et al. [3] arrived at this set of observations by doing a comprehensive test of other types of feedback measurements that are possible at a source. Traditional measurements, such as most recent RTT sample or a smoothed estimate of the RTT sample, were tested and discarded because it was observed that they did not improve the performance of the resulting protocol. In particular, Remy does not make use of two variables that almost every other TCP algorithm uses: the packet drop rate p and the round trip latency T. The packet drop rate is not used because a well-functioning algorithm should naturally lead to networks with small queues and very few losses. The round trip latency T was intentionally kept out because the designers did not want the algorithm to take T into account in figuring out the optimal action to take.

Note that Remy does not keep memory from one busy period to the next at a source, so that all the estimates are reset every time a busy period starts.

3.

Control actions: Every time an ACK arrives, Remy updates its observation variables and then does a look-up from a precomputed table for the action that corresponds to the new state. A Remy action has the following three components:

a.

Multiply the current congestion window by b, i.e., W←bW.

b.

Increment the current congestion window by a, i.e., W←W+a.

c.

Choose a minimum of

τ > 0

ms as the time between successive packet sends.

Hence, in addition to the traditional multiplicative decrease/additive decrease actions, Remy implements a combination of window+rate-based transmission policy, where the interval between transmissions does not exceed

τ

seconds.

At a high level, Remy Congestion Control (RemyCC) consists of a set of piecewise constant rules, called the Rule Table, where each rule maps a rectangular region of the observation space to a three dimensional action. On receiving an ACK, RemyCC updates its values for (ack_ewma, send_ewma, rtt_ratio) and then executes the corresponding action (b, a,

τ

We now describe how these rules are generated:

Remy randomly generates millions of different network configurations by picking up random values (within a range) for the link rates, delays, the number of connections, and the on-off traffic distributions for the connections. At each evaluation step, 16 to 100 sample networks are drawn and then simulated for an extended period of time using the RemyCC algorithm. At the end of the simulation, the objective function given by equation 2 is evaluated by summing up the contribution from each connection to produce a network-wide number. The following two special cases were considered:

corresponding to proportional throughput and delay fairness and

which corresponds to minimizing the potential delay of a fixed-length transfer.

RemyCC is initialized with the following default rule that applies to all states: b=1, a=1,

τ = 0.01

. This means that initially there is a single cube that contains all the states. Each entry in the rule table has an “epoch,” and Remy maintains a global epoch number initialized to zero.

The following offline automated design procedure is used to come up with the rule table:

1.

Set all rules to the current epoch.

2.

Find the most used rule in this epoch: This is done by simulating the current RemyCC and tracking the rule that receives the most use. At initialization because there is only a single cube with the default rule, it gets chosen as the most used rule. If we run out of rules to improve, then go to step 4.

3.

Improve the action for the most used rules until it cannot be improved further: This is done by drawing at least 16 network specimens and then evaluating about 100 candidate increments to the current action, which increases geometrically in granularity as they get further from the current value. For example, evaluate

τ \pm 0.01, τ \pm 0.08, τ \pm 0.64, \dots

, while taking the Cartesian product with the choices for a and b. The modified actions are used by all sources while using the same random seed and the same set of specimen networks while simulating each candidate action.

If any of the candidate actions lead to an improvement, then replace the original action by the improved action and repeat the search, with the same set of networks and random seed. Otherwise, increment the epoch number of the current rule and go back to step 2. At the first iteration, this will result in the legacy additive increase/multiplicative decrease (AIMD)–type algorithm because the value of the parameters a, b are the same for every state.

4.: If we run out of rules in this epoch: Increment the global epoch. If the new epoch is a multiple of a parameters K, set to K=4, then go to step 5; otherwise, go to step 1.
5.: Subdivide the most-used rule: Subdivide the most used rule at its center point, thus resulting in 8 new rules, each with the same action as before. Then return to step 1.

An application of this algorithm results in a process whereby areas of the state space that are more likely to occur receive more attention from the optimizer and get subdivided into smaller cubes, thus leading to a more granular action.

Figure 9.1 shows the results of a comparison of TCP Remy with legacy congestion control protocols (the figure plots the throughput averaged over all sources on the y-axis and the average queuing delay at the bottleneck on the x-axis). A 15-mbps dumbbell topology with a round trip of 150 ms and n=8 connections was used, with each source alternating between a busy period that generates an exponentially distributed byte length of 100 Kbytes and an exponentially distributed off time of 0.5 sec. RemyCC is simulated with the utility function in equation 3 and with three different values of

δ

, with higher values corresponding to more importance given to delay. The RemyCC algorithm that was generated for this system had between 162 and 204 rules.

The results in Figure 9.1 show that RemyCC outperformed all the legacy algorithms, even those that have an AQM component, such as CUBIC over CoDel with stochastic fair queuing. Further experimental results can be found in Winstein [3].

Figure 9.1 also illustrates that existing congestion control algorithms can be classified by their throughput versus delay performance. Algorithms that prioritize delay over throughput, such as Vegas, lie in lower right hand corner, and those that prioritize throughput over delay lie in the upper left-hand part of the graph. The performance numbers for RemyCC trace an outer arc, which corresponds to the best throughput that can be achieved, for a particular value of the delay constraint. Thus, this framework provides a convenient way of measuring the performance of a congestion control algorithm and how close they are to the ideal performance limit.

Because of the complexity of the rules that RemyCC uses, so far the reasons of its superior performance are not well understood and are still being actively investigated.