سیاست مدیریت بافر هارمونیک برای سوئیچ های حافظه به اشتراک گذاشته شده

In this paper we consider shared-memory switches. We introduce a novel general non-preemptive buffer management scheme, which considers the queues ordered by their size. We propose a new scheduling policy, based on our general scheme, which we call the Harmonic policy. We analyze the performance of the Harmonic policy by means of competitive analysis and demonstrate that its throughput competitive ratio is at most ln(N)+2, where N is the number of output ports. We also present a lower bound of View the MathML source on the performance of any online deterministic policy. Our simulations also show that the Harmonic policy achieves high throughput and easily adapts to changing load conditions.

The Internet is built around a large variety of transmission and switching systems and the information transfer is aggregated into packets, which are individually forwarded and switched toward their destinations. The main tasks of a router are to receive a packet from an input port, :nd its destination port using the routing table, transfer the packet to the output port via the switch fabric, and :nally transmit it on the output link. If a burst of packets destined to the same output port arrives, not all packets can be transmitted on the ;y and thus some of them need to be bu"ered. A critical aspect of the switch architecture is placement of bu"ers. In the output queuing (OQ) architecture, packets arriving from input ports immediately cross the switching fabric,and join a queue at the switch output port. It is well-known that the OQ architecture allows one to maximize throughput and control packet latency accurately. The shared memory (SM) switch architecture is an OQ architecture in which output queues are dynamically allocated from a shared memory pool. The main bene:t of SM switches is their ;exibility. At the one extreme, they can be used for complete sharing, where the memory is used as one bu"er to serve all the output ports. The main bene:t of complete sharing is that it takes advantage of statistical multiplexing. However, complete sharing may perform poorly under overload conditions [10]. The problem is that a single output port can take over most of the memory, preventing packets destined for other output ports from gaining access, which causes the total switch throughput to drop. At the other extreme, shared memory can also simulate complete partition, i.e. a dedicated bu"er for each output port. In this case the ;ow of each output port is fully protected from the ;ows of other output ports. This comes at the cost of underutilization of resources, thus risking higher loss during bursts. The ;exibility of shared memory allows one to specify many other policies on the spectrum between complete sharing and complete partition. The goal of a bu"er management policy is to achieve as much of the bene:ts of both schemes while su"ering as little as possible from their weaknesses. The bu"er management policies are traditionally classi:ed into two categories: preemptive and non-preemptive, according to whether they utilize the preempt action in which a packet that has been accepted into the bu"er can be later dropped in order to free space for newly arriving packets. The tradeo" here is between ease of implementation and hardware (where non-preemptive policies have an advantage) and higher performance (where preemptive policies have an advantage). Both types of policies have been widely considered in the networking literature. For a good survey of shared-memory bu"er management policies the reader can refer to [2]. The main class of non-preemptive scheduling policies are static threshold schemes. Irland [10] considers some simple policies of this type. In sharing with maximum queue lengths (SMXQ) scheme, each output queue has a static bound on its length and a packet is accepted if there is a free space in the bu"er and the corresponding bound is not violated. In some schemes, like sharing with a maximum queue and minimum allocation (SMQMA) due to Kamoun and Kleinrock [11], each port always has access to a minimum allocated space. The main problem of the static threshold schemes is that they are not adaptive. When many queues are active and the sum of their thresholds exceeds the bu"er capacity, the bu"er may :ll up completely, even though all queues are obeying the threshold constraints. Thus, some queues can be starved, which leads to underutilization of the switch. On the other hand, when very few queues are active, they are denied access to the idle bu"er space beyond the sum of their thresholds. This creates higher packet loss rate for the active queues (see [5]). Another class of non-preemptive policies includes dynamic threshold schemes. In the Dynamic Threshold (DT) policy due to Choudhury and Hahne [5], the threshold on a queue length at any instant of time is proportional to the current amount of unused bu"er space in the switch multiplied by some constant. Packet arrivals for an output port are blocked whenever the corresponding queue length equals or exceeds the current threshold value. The main idea is that the DT policy deliberately holds a small amount of bu"er space in reserve and divides the remaining bu"er space equally among the active output queues. The class of preemptive policies has been also studied extensively. A delayed resolution policy (DRP) was proposed by Thareja and Agrawala in [24]. The DRP does not discard an arriving packet if there is space in the common bu"er. If a packet arrives and the common bu"er is full, the arriving packet, or some other packet that was already accepted, is discarded. The decision to drop a packet from a certain queue can be made based on the state of the system or based on di"erent priority classes. Wei et al. [26] propose the Longest Queue Drop (LQD) policy, which drops a packet from the longest queue in the switch, when the memory is full. Competitive analysis of preemptive scheduling policies appears in [8]. They show that LQD is 2-competitive and present a lower bound of 43 on the competitive ratio of any deterministic online policy. Unfortunately, non-preemptive policies cannot achieve a constant competitive ratio, as we will show in this paper. A comparison of preemptive policies has been provided in [16]. Our model is as follows. We assume that all the packets are of equal size. When a packet arrives, the bu"er management policy determines whether to accept or reject it. Packets cannot be preempted and once a packet is accepted, it is eventually transmitted on the output link. Conceptually, one may think of the packets in the shared memory as partitioned to separate queues destined to distinct output ports. Clearly, the sum of the lengths of the queues is bounded by the size of the shared memory. At every time unit, from every non-empty output queue, the :rst packet is sent on the corresponding output link. In addition, any number of packets destined to di"erent output ports may arrive. The basic goal of the bu"er management policy is that of maximizing the total number of packets transmitted. In this work we introduce a general non-preemptive bu"er management scheme for shared memory packet switches. The main novel idea is to consider not only the size of the queue as a function of the output port, but also the ability to consider the queues sorted by their current size. For example, our scheme allows one to bound the size of the second largest queue, regardless of the identity of the output port. This way one can specify that there will be at most two large queues and the other queues should be of moderate size. Although we specify the number of large queues, we do not specify their identities, thus in the above example any two output ports can take the large allocations. In a nutshell, the scheme allows to bound the length of an individual queue and the total length of a subset of queues. We use competitive analysis [23,4] to study the performance of our policies. In competitive analysis, the online policy is compared with an optimal oMine policy OPT, that knows the entire input sequence in advance. The online algorithm A is called ccompetitive if for any input sequence of packets, the number of packets sent by OPT is at most c times that delivered by A plus a constant independent of . The advantage of competitive analysis is that a uniform performance guarantee is provided over all input instances.