JP3791529B2 - Frame buffer management circuit and method - Google Patents

Description

  The present invention reads a frame by priority control, weighted round robin control or the like on a connection-by-connection basis when a plurality of connections are concentrated or multiplexed in a switch that handles an Ethernet (registered trademark) frame or the like. In particular, the present invention relates to a frame buffer management method and circuit including a buffer for each connection.

  When a plurality of connections are concentrated or multiplexed in a switch on the network, if a single FIFO (First In First Out) type buffer shared between multiple connections is used in the frame readout unit, the occupation rate and discard rate in the buffer However, since the frames are stored in the order of arrival regardless of the connection, the connection accommodating the power user is advantageous in terms of the bandwidth usage and the delay time.

  As a means for ensuring the fairness of the amount of bandwidth used between connections and the delay time, for example, there is a method of using a FIFO buffer individually for each connection. However, if the individual FIFO type buffer is mounted by the memory occupation method, the use efficiency of the memory is lowered, so that it is necessary to prepare a large memory capacity.

  Mounting many memories in a device is disadvantageous in terms of mounting area and cost. Therefore, by dynamically allocating and releasing the memory for the buffer as necessary, the memory is shared between the connections and the usage efficiency is improved (for example, see Non-Patent Document 1).

JP-A-11-32055

  In the above method, a pointer chain (link) is used for managing the shared buffer memory. Since the pointer chain connects the buffer memory by a link, the management of the buffer memory becomes complicated and the processing time increases. When the capacity of the switch is increased, the processing time that can be given to one frame is shortened, and there is a possibility that the processing may not be in time.

  In addition, since it is necessary to hold information for linking the buffer memory, a memory capacity for linking is separately secured. If the link memory is arranged as a memory chip different from the buffer memory, the mounting area and the number of mounting pins increase.

  Further, the above method assumes the accommodation of fixed-length frames such as ATM cells. When handling variable-length frames such as Ethernet (registered trademark) frames, if memory blocks are prepared according to the maximum frame length, the memory usage efficiency decreases when storing short frames, thus reducing the influence of the frame length. There is a need. These can be limitations at the time of implementation.

  Therefore, the present invention realizes fair reading in terms of bandwidth usage and delay time for variable-length frames such as Ethernet (registered trademark) frames, increases the memory usage efficiency, and is managed by the link. An object of the present invention is to provide a frame buffer management circuit that can increase the speed.

According to the present invention, a frame buffer that accommodates one or more connections, has a FIFO-type data structure for each connection, and dynamically allocates and releases memory shared among all connections as individual connection buffers. In the management circuit,
Frame distribution means for determining an allocation destination buffer for the input frame based on attribute information recorded in the frame header part or a setting value given in advance;
Frame accumulation means configured as a set of memory blocks and storing the entity of the input frame;
A buffer memory block address management means having a FIFO type data structure, comprising a connection buffer, instructing and managing a memory block which is a part of the frame storage means by a pointer;
A queue management means for indicating and managing the head position and the tail position of the connection buffer with a pointer;
Free memory block management means for indicating and managing memory blocks not used in the frame storage means by pointers;
Frame length management means for holding the length of the frame accommodated in the connection buffer;
Accumulation / reading / discarding discriminating means for discriminating whether to perform a storage, reading, or discarding operation from a frame to be operated based on information on the frame accumulation state of the buffer;
Frame reading means for reading a frame from the frame storage means;
Frame discarding means for discarding a frame when the frame cannot be stored in the buffer.

  According to another embodiment of the frame buffer management circuit of the present invention, it is also preferable to provide connection group information management means for handling a buffer management unit as a connection group, a route, or a combination thereof instead of a single connection. .

  According to another embodiment of the frame buffer management circuit of the present invention, each connection includes multi-buffer management means for holding and managing a buffer for each of one or more QoS classes or ports, and the multi-buffer management means includes a connection It is also preferable to provide buffer memory block management means for accommodating one or more QoS classes or ports in the inside, and queue management means for accommodating one or more QoS classes or ports in the connection.

  Furthermore, according to another embodiment of the frame buffer management circuit of the present invention, one or more blocks constituting the buffer memory block address management means are grouped, and each group is used as a part of the buffer memory block address management means. It is also preferable to provide address group management means for performing allocation and release.

  Furthermore, according to another embodiment of the frame buffer management circuit of the present invention, the buffer usage monitoring means for monitoring the buffer usage status of each connection, and the buffer memory based on the information acquired from the buffer usage status monitoring means It is also preferable to provide a maximum queue length determining means for dynamically determining the maximum queue length used by the block address management means.

  Furthermore, according to another embodiment of the frame buffer management circuit of the present invention, the length of the frame accommodated in the frame buffer is set in the memory block included in the frame storage means instead of the frame length management means. It is also preferable to provide an extended frame storage means for recording together.

  Furthermore, according to another embodiment of the frame buffer management circuit of the present invention, it is preferable that the frame buffer management circuit further comprises priority discard frame selection means for selecting a frame to be discarded preferentially.

Further, according to the present invention, one or more connections are accommodated, each connection has a FIFO type data structure, and a memory shared between all connections is dynamically allocated and released as individual connection buffers. In the frame buffer management method,
A frame distribution step for determining an allocation destination buffer based on attribute information recorded in the frame header part or a setting value given in advance for the input frame;
A frame accumulating step configured as a set of memory blocks and storing the entity of the input frame;
A buffer memory block address management step that configures a connection buffer and is a FIFO type data structure, and indicates and manages a memory block that is a part by a pointer;
A queue management step for indicating and managing the start position and the end position of the connection buffer with pointers;
A free memory block management step for pointing and managing unused memory blocks with a pointer;
A frame length management step for holding the length of the frame accommodated in the connection buffer;
An accumulation / reading / discarding discrimination step for discriminating whether to perform an operation of accumulation, reading, or discarding from a frame to be operated based on information on a frame accumulation state of the buffer;
A frame reading step for reading the accumulated frames;
A frame discarding step for discarding the frame when the frame cannot be stored in the buffer.

  According to another embodiment of the frame buffer management method of the present invention, it is also preferable to have a connection group information management step in which a buffer management unit is handled as a connection group or a route or a combination thereof instead of a single connection. .

  According to another embodiment of the frame buffer management method of the present invention, each connection has a multi-buffer management step for holding and managing a buffer for each of one or more QoS classes or ports, and the multi-buffer management step includes: It is also preferable to include a buffer memory block management step for accommodating one or more QoS classes or ports in the connection, and a queue management step for accommodating one or more QoS classes or ports in the connection.

  Furthermore, according to another embodiment of the frame buffer management method of the present invention, one or more blocks constituting the buffer memory block address management means are grouped, and each group is used as a part of the buffer memory block address management means. It is also preferable to have an address group management step for assigning and releasing.

  Furthermore, according to another embodiment of the frame buffer management method of the present invention, a buffer usage monitoring step for monitoring the buffer usage status of each connection, and a buffer memory based on information acquired from the buffer usage status monitoring step It is also preferable to have a maximum queue length determination step that dynamically determines the maximum queue length used in the block address management step.

  Furthermore, according to another embodiment of the frame buffer management method of the present invention, the length of the frame accommodated in the frame buffer is combined with the entity of the frame in the accumulated memory block instead of the frame length management step. It is also preferable to provide an extended frame storage step for recording.

  Furthermore, according to another embodiment of the frame buffer management method of the present invention, it is preferable to further comprise a priority discard frame selection step for selecting a frame to be discarded preferentially.

  According to the frame buffer management circuit of the present invention, by configuring a logical individual FIFO buffer, it is fair in terms of bandwidth usage and delay time over variable length frames such as Ethernet (registered trademark) frames. While making reading possible, the memory usage efficiency is increased by sharing the memory between connections. By monitoring the usage rate of the shared memory and limiting the maximum queue length, it is possible to prevent a specific connection from occupying the memory. By managing the constituent elements of the individual FIFO type buffer by the queue, the management is simplified and speeded up than the management by the link. By performing the discard operation based on the priority, it is possible to prevent the discard of the frame having a high priority.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

<Embodiment 1 based on the invention according to claim 1>
In the first embodiment, by configuring a logical individual FIFO type buffer, it is possible to achieve fair reading in terms of bandwidth usage and delay time, while increasing the use efficiency by sharing memory between connections. In addition, the individual FIFO buffer management is simplified by using a queue, and is faster than the management by a link.

  FIG. 1 is a configuration diagram of a frame buffer management circuit.

  The frame buffer management circuit 1 includes a frame distribution unit 101, a frame storage unit 102, a storage / read / discard determination unit 103, a buffer memory block address management unit 104, a queue management unit 105, a free memory block management unit 106, a frame length It comprises a management unit 107, a frame reading unit 109, and a frame discarding unit 110.

  The frame input to the frame buffer management circuit 1 is read out by the frame sorting unit 101 and the frame information described in the header is read out and stored in the frame storage unit 102. The frame stored in the frame storage unit 102 is output as a frame by the frame reading unit 109 or discarded by the frame discarding unit 110 according to a command from the storage / reading / discarding determination unit 103.

  The accumulation / read / discard discriminating unit 103 determines a method of processing frames to be accumulated in the frame accumulation unit 102 by using a frame input from the frame distribution unit 101 or a read command from outside the frame buffer management circuit as a trigger. In order to determine a frame processing method, frame information is acquired from the frame allocation unit 101, buffer usage status information is acquired from the free memory block management unit 106, and an individual FIFO is received from the buffer memory block address management unit 104. Information on the memory accumulation status of the type buffer is acquired. When the storage / read / discard discriminating unit 103 determines the frame processing method, the buffer memory block address management unit 104 reflects the change in the state of the individual FIFO type buffer.

  The buffer memory block address management unit 104 manages the state of the individual FIFO buffer in cooperation with the queue management unit 105.

  When the state of the frame storage unit 102 changes according to a command from the storage / read / discard discriminating unit 103, the state of the memory block is managed in cooperation with the free memory block management unit 106 and the frame length management unit 107.

  FIG. 2 is a configuration diagram of a logical frame buffer management circuit.

  The frame buffer management circuit 1 includes a frame distribution unit 101, an individual FIFO buffer, and a frame reading unit 109.

  For the frame input to the frame buffer management circuit 1, an individual FIFO type buffer accommodated in the frame distribution unit 101 is selected. Each individual FIFO type buffer behaves as a logically independent buffer. The frame reading unit 109 reads a frame from the individual FIFO type buffer by priority control or weighted round robin control.

  The individual FIFO type buffer is configured by the memory block of the frame storage unit 102 in FIG. 1, but since the memory block is shared between connections, the maximum queue length of each individual FIFO type buffer varies depending on the frame storage status. Changes.

  FIG. 3 is a buffer configuration diagram of each function based on FIG.

  The frame storage unit 102, the buffer memory block address management unit 104, the queue management unit 105, the free memory block management unit 106, and the frame length management unit 107 are each configured on a memory as shown in FIG. The frame storage unit 102 is configured by a memory block having a fixed length (for example, 512 bytes).

  FIG. 4 is an explanatory diagram showing the relationship between the frame storage unit and the accommodation frame.

  Each memory block stores a frame entity (Payload). If the length of the frame to be stored is longer than the memory block length, it is divided and a plurality of memory blocks are used. If the boundary of the memory block does not match the boundary of the frame to be stored, the empty space is filled with padding. Note that the padding area may be filled with an indefinite value (Don't care) in addition to the specific pattern value.

  FIG. 5 is an explanatory diagram showing the relationship between the frame storage unit and the buffer memory address management unit.

  The buffer memory block address management unit 104 includes a pointer that points to the memory block of the frame storage unit 102. The pointers in the buffer memory block address management unit 104 are collected as a plurality of continuous blocks, and are associated with each connection. For example, the pointers to the addresses # 1 to #q in FIG. 3B are associated with the connection # 1 (ID # 1). A pointer associated with the same connection is handled as a queue (FIFO) type data structure.

  The queue management unit 105 indicates a queue range for each connection in the buffer memory block address management unit 104, and includes a pair of a pointer (Head) indicating the head and a pointer (Tail) indicating the tail. The number of pairs of pointers indicating both ends of the queue is the same as the number of queues (number of connections) associated in the buffer memory block address management unit.

  FIG. 6 is an explanatory diagram showing the relationship between the buffer length memory block address management unit and the queue length management unit.

  When the area in use in each queue of the buffer memory block address management unit 104 changes, the value of the pointer of the queue length management unit 105 changes accordingly. The buffers constituting the queue for each connection of the buffer memory block address management unit 104 are handled as being continuous in a ring shape. For this reason, as shown in FIG. 6D, the magnitude relationship between the addresses stored in the two pointers of the queue length management unit 105 may be reversed (Tail <Head). In this case, in the physical memory arrangement, the trailing pointer (address #q in FIG. 6D) is followed by the leading pointer (address # 1 in FIG. 6D).

  7A and 7B are explanatory diagrams showing the relationship between the frame storage unit and the free memory block management unit.

  The empty memory block management unit 106 includes the same number of pointers as the memory blocks of the frame storage unit 102. The empty memory block is handled as a stack (FILO: First In Last Out) type data structure, and a stack pointer is prepared to indicate the current use position. The free memory block pointer indicates a memory block not used by the frame storage unit 102. As shown in FIG. 7A (b), when using memory blocks by frame input, the memory blocks designated by the empty memory block management unit 106 are sequentially used to move the stack pointer. As shown in FIG. 7B (c), when the memory block is released by frame output, the address of the released memory block is recorded in the empty area of the empty memory block management unit 106 in order, and the stack pointer is moved.

  In the first embodiment, the free memory block management unit has a stack type data structure. However, like the buffer memory block address management unit, a queue type data structure is formed using two pointers, Head and Tail. You can also.

  FIG. 8 is an explanatory diagram showing the relationship between the frame storage unit and the frame length management unit.

  The frame length management unit 107 is composed of the same number of data areas as the memory blocks of the frame storage unit 102. When frames are stored in the memory block, the frame storage unit 102 and the frame length management unit 107 store information related to the position of the same address. For example, the frame length information related to the address # x + 1 of the frame storage unit is stored at the address # x + 1 of the frame length management unit. In the data area of the frame length management unit 107, frame length information of a frame stored in the associated frame storage unit 102 is stored. As the frame length information, for example, the length from the beginning of the corresponding memory block to the end of the frame is stored. In this method, even when the frame is divided because it exceeds the memory block length, the memory block constituting the frame end can be determined. Furthermore, the remaining frame length can be determined from the position of an arbitrary memory block. As another method for expressing the frame length information, a combination of a flag indicating the flag end and the length of the frame entity in the memory block may be used.

  FIG. 9 is a flowchart at the time of frame input / output in the frame buffer management circuit.

FIG. 9A illustrates a flow at the time of frame input.
(S1) A frame is input (S2) The frame distribution unit selects a buffer memory block management unit that accommodates the input frame, and sends the frame information to the storage / read / discard discrimination unit.
(S3) The accumulation / read / discard discriminating unit checks whether there is a vacancy in the buffer memory block address management unit. If there is no vacancy, (S8) discards the input frame.
(S4) The storage / read / discard discriminating unit checks with the free memory block management unit whether there is a free space in the frame storage unit.
(S5) When there is no free space in the frame storage unit, the storage / reading / discarding determination unit refers to the individual queue information for each connection held by the buffer memory block address management unit and determines a frame to be discarded. If the incoming frame is to be discarded, (S8) the incoming frame is discarded.
(S6) If the frame of another connection should be discarded, the corresponding frame is discarded.
(S7) The address of the free memory block is read from the free memory block management unit.
(S8) The frame length information is written in the frame length management table using the read address as a key.
(S9) The contents of the frame are written with the free memory block size in the frame storage unit as the upper limit.
(S10) The queue information in the buffer memory block address management unit is updated.
(S11) It is determined whether the corresponding memory block handles the tail of the input frame. If it is the tail, the process ends. If it is not the tail, accumulation processing of the subsequent frames is performed from (S7).

Next, the flow at the time of outputting a frame in FIG. 9B will be described.
When a frame read command is given to the accumulation / read / discard discriminator,
(S1) The address in the frame storage unit where the frame is recorded is read from the buffer memory block address management unit.
(S2) The frame length information is read from the frame length management table.
(S3) The content of the frame divided with the memory block size as the upper limit is read from the memory block in the frame storage unit.
(S4) The queue information in the buffer memory block address management unit is updated using the read address as a key.
(S5) An address of an unnecessary memory block is written in the empty memory block management unit to make an empty memory block.
(S6) It is determined whether the corresponding memory block handles the tail of the output frame, and if it is not the tail, the subsequent frame reading process from (1) is performed.
(S7) The original frame is reconstructed from the divided frames.
(S8) The reconstructed frame is output.

  As another embodiment of the first embodiment, since a frame to be accumulated is larger than a memory block, when the frame is divided into a plurality of memory blocks and managed, the frame is configured using a pointer provided in the memory block. Some connect by indicating a memory block.

  FIG. 10 is an explanatory diagram of a management method when a frame is divided into a plurality of memory blocks.

  FIG. 10A uses the pointer of the buffer memory block address management unit 104 for each divided memory block by the method described in the first embodiment. In other words, if the number of memory blocks constituting one frame is large, a large number of pointers in the buffer memory block address management unit 104 are used.

  On the other hand, in FIG. 10B, the pointer of the buffer memory block address management unit 104 indicates the memory block corresponding to the head of the frame, but the subsequent memory blocks are included in the head memory block. This is indicated by the provided pointer. As a result, regardless of the number of memory blocks constituting one frame, the pointer of the buffer memory block address management unit used for one frame can be made one.

  When the maximum number of memory blocks constituting one frame is small, the pointer area in the memory block at the head of the frame may be secured, but when the maximum number of memory blocks constituting one frame becomes large In order to effectively use the memory, it is advantageous to dynamically provide a pointer area as much as necessary depending on the frame length.

  Similarly, in FIG. 10C, a memory block constituting a frame is indicated by a pointer provided in the memory block. In this configuration, even if the number of memory blocks constituting a frame increases, the ratio of pointer areas in the memory blocks does not change, so there is no need to dynamically provide pointer areas. Therefore, the management of the memory block can be simplified as compared with FIG.

  By applying the configuration of this embodiment, the buffer memory block address management unit 104 designates only the memory block at the head of the frame, thereby simplifying the size reduction and memory block management of the buffer memory block address management unit 104. Has the effect of

<Embodiment 2 of the invention according to claim 2>
The second embodiment is characterized in that the unit accommodated and managed in the individual FIFO buffer shown in FIG. 2 is not limited to a single connection, but is handled as a connection group or a route or a combination thereof.

  As a means for identifying a connection, for example, an Ethernet (registered trademark) frame has a MAC (Media Access Control) address and a VLAN (Virtual LAN) tag, and an ATM (Asynchronous Transfer Mode) cell has a VPI (Virtual Path Identifier) / VCI (Virtual Channel). Identifier) can be used. It can also be associated with a physical port mounted on the device.

  The connections identified by the above-described means can be individually accommodated in the buffer, but in some cases, a plurality of connections may be handled as a group. When connections are grouped, they are handled as a single connection as a connection group and are accommodated in the same individual FIFO buffer.

  FIG. 11 is a configuration diagram of a frame buffer management circuit corresponding to connection grouping.

  FIG. 11 differs from FIG. 1 in that the connection group information management unit 111 is provided. The connection grouping is realized by referring to the connection information held by the input frame and the correspondence information of the connection and group held by the connection group information management unit.

  By applying the configuration of this embodiment, the number of connections (groups) to be handled can be reduced, and the circuit scale can be reduced.

<Third embodiment of the invention according to claim 3>
The third embodiment is characterized in that the unit accommodated and managed in the individual FIFO buffer shown in FIG. 2 is handled as one or more QoS classes or ports set for each connection.

  FIG. 12 is a configuration diagram of a frame buffer management circuit including a multi-buffer in a connection.

  FIG. 12 differs from FIG. 1 in that the buffer memory block address management unit 1120 and the queue management unit 1121 are provided with a multi-buffer management unit corresponding to multi-class or multi-port.

  FIG. 13 is a memory configuration diagram of a buffer memory block address management unit that accommodates multiple classes in a connection. FIG. 14 is a memory configuration diagram of a queue management unit that accommodates multiple classes in a connection. Compared with those shown in FIGS. 3B and 3C, the portions where the areas for each class are provided in each connection are different.

  FIG. 15 is a configuration diagram of a logical frame buffer management circuit. By allocating an individual FIFO type buffer for each class, as shown in FIGS. 15A and 15B, it is possible to perform bandwidth allocation in a hierarchy for each class or connection.

  In the case of the configuration shown in FIG. 15A, the allocatable bandwidth is distributed for each connection, and the distributed bandwidth is distributed among the classes in the connection. That is, priority is given to bandwidth distribution for connections over bandwidth distribution for classes. Thus, for example, if round-robin reading or overlapped round-robin reading is applied to the subsequent frame reading unit, it is possible to perform bandwidth allocation between classes while maintaining fairness regarding bandwidth allocation between connections.

  In the case of the configuration of FIG. 15B, all allocatable bandwidths are distributed for each class, and the distributed bandwidth is distributed among connections having the corresponding class. That is, priority is given to bandwidth distribution for classes over bandwidth distribution for connections. Thus, for example, if priority reading is applied to the frame reading unit in the subsequent stage, the bandwidth allocation is applied to the sum of the same class of each connection in the frame buffer management circuit (the range enclosed by the broken line in FIG. 15B). The priority can be set, and the maximum bandwidth and the guaranteed bandwidth can be set by applying round robin reading or weighted round robin reading to the subsequent frame reading unit.

  By applying the configuration of the present embodiment, there is an effect that the handled connection can accommodate a plurality of QoS classes having different bandwidth setting parameters.

  In FIGS. 13 and 14, the number of classes assigned to each connection is the same, but the number of classes may be different for each connection.

<Embodiment 4 of the invention according to claim 4>
The fourth embodiment is characterized in that if an address group is formed by grouping a plurality of pointers in the buffer memory block address management unit, a use area of the address group is dynamically allocated.

  FIG. 16 is a configuration diagram of a frame buffer management circuit corresponding to the address grouping of the buffer memory block address management unit.

  FIG. 16 is different from FIG. 1 in that the address group management unit 113 is provided. The address group management unit 113 manages allocation and release of address groups.

  FIG. 17 is a memory configuration diagram of a buffer memory block address management unit that dynamically changes the buffer length by grouping pointers.

  In the fourth embodiment, the buffer memory block address management unit is divided into a plurality of groups, and one or more pointers (Pointer) for designating memory blocks and a pointer (Next) for connecting groups are grouped. The buffer memory block address management unit 104 dynamically allocates / releases buffers in groups as necessary. If each connection has a frame input and a new buffer is required, it is assigned in groups and added to the buffer. If there is a frame output and all pointers are unused in the group that constitutes the buffer, the unused group can be released from the buffer and used as a buffer for other connections. To do.

  FIG. 18 is an explanatory diagram showing the relationship between the frame storage unit, the buffer memory address management unit grouped, and the queue length management unit.

  Except that the buffer memory address management unit 104 is grouped, it is the same as FIG. In order to connect each group, a group connection pointer (Next) included in the group is used. The group connection pointer indicates the ID of the group to be connected next. If no group is connected to the back, a value (for example, NULL) indicating the end is stored in the group connection pointer.

  19A and 19B are flowcharts at the time of frame input / output.

  FIG. 19A (a) is a flow at the time of frame input. Compared to FIG. 9A, the part where (S4) and (S5) are added is different. FIG. 19B (b) is a flow at the time of frame output. Compared to FIG. 9B, the part where (S6) and (S7) are added is different.

  By applying the configuration of the fourth embodiment, the maximum length of each individual FIFO type buffer of the buffer memory block address management unit 104 can be extended. The discarding of the frame that occurs because the memory block address management unit 104 has no space is suppressed. That is, the use efficiency of the buffer memory block address management unit 104 is improved.

  In the fourth embodiment, a link between unidirectional groups is established by preparing a Next pointer in the buffer memory block address management unit 104. However, a bidirectional link or a separate group management table is used. May be.

<Embodiment 5 of the invention according to claim 5>
The fifth embodiment is characterized in that the individual FIFO type buffer usage status of each connection shown in FIG. 2 is monitored, and the maximum queue length of the individual FIFO type buffer is made variable based on the usage status.

  FIG. 20 is a configuration diagram of a frame buffer management circuit capable of changing the maximum queue length.

  20 is different from FIG. 1 in that a buffer usage monitoring unit 114 and a maximum queue length determination unit 115 are provided. When the storage / read / discard discrimination unit 103 instructs the buffer memory block address management unit 104 to input / output a frame, the buffer memory block address management unit 104 inputs a frame to the buffer usage status monitoring unit 114. Notify output information. The buffer usage status monitoring unit 114 holds the current queue state of each individual FIFO buffer for each connection. A condition for changing the maximum queue length is set in advance in the buffer usage status monitoring unit 114. When this condition is satisfied, the maximum queue length determination unit 115 is notified. Upon receiving this notification, the maximum queue length determination unit 115 determines the maximum queue length to be reflected, and notifies the buffer memory block address management unit 104 of the maximum queue length information. The buffer memory block address management unit 104 reflects the notified queue length information, and controls so that the queue of the individual FIFO buffer of the connection does not extend beyond this value.

  The conditions for the maximum queue length determination unit to update the maximum queue length include, for example, excess / non-exceeding of a threshold regarding the buffer (memory block) usage at a certain time, or the total buffer (memory block) usage at a certain time. There is an excess / non-exceed threshold.

  By applying the configuration of the fifth embodiment, it is possible to prevent a specific connection from using a memory block ubiquitously and preventing other connections from using the memory block, resulting in an unfair allocation of bandwidth. effective.

<Embodiment 6 of the invention according to claim 6>
The sixth embodiment is characterized in that the frame length management unit shown in FIG. 3 (e) is integrated with the frame storage unit shown in FIG. 3 (a), and an extended frame length management unit is provided.

  FIG. 21 is a configuration diagram of the extended frame storage unit.

  The frame length management unit 107 stores the length of the frame stored in the corresponding frame storage unit 102. The memory area required to store the frame length is at most several bytes. Considering storing an Ethernet (registered trademark) frame, the memory area of the memory block of the frame storage unit 102 is on the order of 100 bytes even if the maximum frame length is divided into portions of about 2-10. Therefore, even if a field for storing the frame length is added to the frame storage unit 102, the influence on the frame storage unit 102 in terms of capacity and the number of memory blocks that can be accommodated is small.

  On the other hand, by integrating the frame storage unit 102 and the frame length management unit 107, the number of memory chips to be mounted can be reduced. By reducing the number of memory chips to be mounted, the number of pins for accessing the memory chip can be reduced, so that the degree of freedom of mounting is expanded.

  Since two pieces of information of the frame entity and the frame length are always handled as a pair, the management can be simplified by integrating them and managing them individually.

  By applying the configuration of the sixth embodiment, there is an effect of simplifying memory management and expanding the degree of freedom of physical mounting.

<Embodiment 7 of Invention of Claim 7>
The seventh embodiment is characterized in that a discard priority is set according to connection and frame attributes, and a frame to be discarded preferentially is selected.

  FIG. 22 is a configuration diagram of a frame buffer management circuit for realizing priority discard.

  FIG. 22 differs from FIG. 1 in that a priority discard frame selection unit 116 is provided. In addition, a buffer usage status monitoring unit 114 may be provided for the purpose of collecting information for selecting priority discard frames. When there is a frame input in the frame buffer management circuit 1, the accumulation / read / discard discrimination unit 103 discriminates the processing method of the incoming frame. If there is no free space in the memory block of the frame accumulation unit 102, it is inputted. Discard either the frame or the already stored frame.

  To determine the frame to be discarded, the frame to be discarded is determined only by the attribute of the frame or connection, and the frame to be discarded is determined in consideration of the buffer usage information in addition to the frame or connection attribute. There is a case. An example of the operation in each case is shown below.

  When determining a frame to be discarded based on the attribute of the frame, priority information in the frame, for example, priority bit information to be set in a VLAN tag with priority or TOS (Type of Service of IP packet) is used as information for determination. ) Information etc. can be used. The priority of the input frame and the priority of the stored frame are managed, and if the priority of the newly input frame is low, it is discarded as it is, but if the priority of the input frame is high, it is stored Discard from the low priority frame in the frame.

  When determining the frame to be discarded based on the connection attribute, the priority class information set for the connection can be used. When there are a bandwidth guarantee type class and a best effort type class, the best effort type class has a lower priority. Therefore, the frame of the best-effort class with low priority is discarded first.

  When a discard frame is determined by adding the buffer usage status information to the static information described above, the discard target frame dynamically changes depending on the traffic status.

  For example, a determination is made based on the amount of memory block usage in the buffer for each connection, and a connection with a large memory block usage is discarded first. Alternatively, the determination can be made on the basis of the memory block amount used within a certain time that goes back with the measurement time as a reference.

  By applying the configuration of the seventh embodiment, it is possible to provide priority services such as preventing the discard of high priority frames by preferentially discarding low priority frames. By discarding from the frame, the effect of ensuring fairness between connections, such as preventing some users, such as power users, from using the shared buffer resources exclusively and causing other users to reduce the throughput, etc. There is.

It is a block diagram of a frame buffer management circuit. It is a block diagram of a logical frame buffer management circuit. It is a buffer block diagram of each function based on FIG. It is explanatory drawing which shows the relationship between a frame storage part and an accommodation frame. It is explanatory drawing which shows the relationship between a frame storage part and a buffer memory address management part. It is explanatory drawing which shows the relationship between a buffer length memory block address management part and a queue length management part. It is explanatory drawing which shows the relationship between a frame storage part and an empty memory block management part. It is explanatory drawing which shows the relationship between a frame storage part and an empty memory block management part. It is explanatory drawing which shows the relationship between a frame storage part and a frame length management part. It is a flowchart at the time of frame input / output in the frame buffer management circuit. It is explanatory drawing of the management method when dividing | segmenting a flame | frame into several memory blocks. It is a block diagram of a frame buffer management circuit corresponding to connection grouping. It is a block diagram of the frame buffer management circuit provided with a multi-buffer in a connection. It is a memory block diagram of the memory block address management part for buffers which accommodates a multi class in a connection. It is a memory block diagram of the queue management part which accommodates a multiclass in a connection. It is a block diagram of a logical frame buffer management circuit. It is a block diagram of the frame buffer management circuit corresponding to the address grouping of the buffer memory block address management unit. It is a memory block diagram of the buffer memory block address management part which changes a buffer length dynamically by the grouping of a pointer. It is explanatory drawing which shows the relationship between the buffer memory address management part grouped with the frame storage part, and the queue length management part. It is a flowchart at the time of frame input / output. It is a flowchart at the time of frame input / output. It is a block diagram of a frame buffer management circuit capable of varying the maximum queue length. It is a block diagram of an extended type frame storage part. It is a block diagram of the frame buffer management circuit which implement | achieves priority discard.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Frame buffer management circuit 101 Frame allocation part 102 Frame accumulation part 103 Accumulation / reading / discard discrimination part 104 Buffer memory block address management part 105 Queue management part 106 Empty memory block management part 107 Frame length management part 109 Frame reading part 110 Frame discard unit 111 Connection group information management unit 112 Multi-buffer management unit 1120 Multi-class / ported buffer memory block address management unit 1121 Multi-class / ported queue management unit 113 Address group management unit 114 Buffer usage status monitoring unit

Claims (14)

In a frame buffer management circuit that accommodates one or more connections, has a FIFO type data structure for each connection, and dynamically allocates and releases memory shared among all connections as individual connection buffers.
Frame distribution means for determining an allocation destination buffer for the input frame based on attribute information recorded in the frame header part or a setting value given in advance;
Frame accumulation means configured as a set of memory blocks and storing the entity of the input frame;
A buffer memory block address management means having a FIFO type data structure, comprising a connection buffer, instructing and managing a memory block which is a part of the frame storage means by a pointer;
A queue management means for indicating and managing the head position and the tail position of the connection buffer with a pointer;
Free memory block management means for indicating and managing memory blocks not used in the frame storage means by pointers;
Frame length management means for holding the length of the frame accommodated in the connection buffer;
Accumulation / reading / discarding discriminating means for discriminating whether to perform a storage, reading, or discarding operation from a frame to be operated based on information on the frame accumulation state of the buffer;
Frame reading means for reading a frame from the frame storage means;
A frame buffer management circuit comprising: frame discarding means for discarding a frame when frames cannot be stored in the buffer.   2. The frame buffer management circuit according to claim 1, further comprising connection group information management means for handling a buffer management unit as a connection group, a route, or a combination thereof instead of a single connection. Each connection has a multi-buffer management means for holding and managing a buffer for each one or more QoS classes or ports,
The multi-buffer management means includes the buffer memory block management means for accommodating one or more QoS classes or ports in a connection;
The frame buffer management circuit according to claim 1, further comprising the queue management unit that accommodates one or more QoS classes or ports in a connection.   One or more blocks constituting the buffer memory block address management means are grouped, and address group management means is provided for performing allocation and release as a part of the buffer memory block address management means for each group. The frame buffer management circuit according to any one of claims 1 to 3. Buffer usage monitoring means for monitoring the buffer usage of each connection;
5. A maximum queue length determination unit that dynamically determines a maximum queue length used by the buffer memory block address management unit based on information acquired from a buffer usage status monitoring unit. The frame buffer management circuit according to any one of the above.   An extended frame storage means for recording the length of the frame accommodated in the frame buffer together with the substance of the frame in a memory block included in the frame storage means, instead of the frame length management means. The frame buffer management circuit according to any one of claims 1 to 5.   7. The frame buffer management circuit according to claim 1, further comprising priority discard frame selection means for selecting a frame to be discarded preferentially. In a frame buffer management method for accommodating one or more connections, having a FIFO-type data structure for each connection, and dynamically allocating and releasing memory shared among all connections as individual connection buffers,
A frame distribution step for determining an allocation destination buffer based on attribute information recorded in the frame header part or a setting value given in advance for the input frame;
A frame accumulating step configured as a set of memory blocks and storing the entity of the input frame;
A buffer memory block address management step that configures a connection buffer and is a FIFO type data structure, and indicates and manages a memory block that is a part by a pointer;
A queue management step for indicating and managing the start position and the end position of the connection buffer with pointers;
A free memory block management step for indicating and managing the memory blocks that are not used by a pointer;
A frame length management step for holding the length of the frame accommodated in the connection buffer;
An accumulation / reading / discarding discrimination step for discriminating whether to perform an operation of accumulation, reading, or discarding from a frame to be operated based on information on a frame accumulation state of the buffer;
A frame reading step for reading the accumulated frames;
A frame buffer management method comprising: a frame discarding step for discarding a frame when the frame cannot be stored in the buffer.   9. The frame buffer management method according to claim 8, further comprising a connection group information management step in which a buffer management unit is handled as a connection group, a route, or a combination thereof instead of a single connection. A multi-buffer management step in which each connection holds and manages a buffer for each of one or more QoS classes or ports;
The multi-buffer management step includes a buffer memory block management step for accommodating one or more QoS classes or ports in the connection, and a queue management step for accommodating one or more QoS classes or ports in the connection. The frame buffer management method according to claim 8 or 9.   One or more blocks constituting the buffer memory block address management means are grouped, and an address group management step is performed for assigning and releasing each group as part of the buffer memory block address management means. The frame buffer management method according to any one of claims 8 to 10. A buffer usage monitoring step for monitoring the buffer usage of each connection;
12. A maximum queue length determining step for dynamically determining a maximum queue length used in the buffer memory block address management step based on information acquired from a buffer usage status monitoring step. The frame buffer management method according to any one of the above.   9. The extended frame storage step for recording the length of a frame accommodated in a frame buffer together with the substance of the frame in the stored memory block, instead of the frame length management step. 13. The frame buffer management method according to any one of items 1 to 12. 14. The frame buffer management method according to claim 8, further comprising a priority discard frame selection step of selecting a frame to be discarded preferentially.

Images