JP3144386B2 - Back pressure control method and device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method and an apparatus for controlling a back pressure of a packet switch for outputting an input packet to a predetermined destination.

[0002]

2. Description of the Related Art Conventionally, as a back pressure control method in a packet switch, for example, Japanese Patent Laid-Open Publication No.
As disclosed in Japanese Patent Application Publication No. 54-54, an input buffer and an output buffer are provided as a switch configuration for back pressure control, and an asynchronous transfer mode (Asynchronous) is provided.
Switching is performed for fixed-length packets such as Transfer Mode (ATM) cells, and input to an output buffer is restricted in fixed packet length units.

On the other hand, as described in Japanese Patent Application Laid-Open No. 9-181740, a configuration is known in which a management cell for resource management is used to limit the output of packets at the ATM cell level.

[0004]

However, Japanese Patent Application Laid-Open No. Hei 8-504554 and Japanese Unexamined Patent Publication No. Hei 9-1817 disclose the above.
As described in Japanese Patent Application Publication No. 40 (1994), in the conventional back pressure control method, in a situation where a packet is divided into fixed-length packets called ATM cells and the back pressure is being executed, the packets are not considered and the ATM cells are not considered. On the other hand, back pressure is executed, and there is a possibility that some ATM cells constituting the packet are discarded in the input buffer, thereby executing back pressure. For this reason, there is a problem that it is necessary to discard incomplete packets on the output buffer side or in packet reassembly.

SUMMARY OF THE INVENTION The present invention has been made in view of the above points, and provides a back pressure control method and apparatus for ensuring the back pressure fairness under a packet input condition by effectively using a packet memory. Aim.

[0006]

According to a first aspect of the present invention, there is provided a back pressure control method for a packet switch for outputting an input packet to a predetermined destination, wherein the packet length of the input packet is shared. It counts based on a threshold value set in advance by the back pressure counter, and when the packet length counted by the shared back pressure counter exceeds the threshold value of the shared back pressure counter, it is set in advance by the individual back pressure counter. The packet length is counted based on the threshold value.

According to a second aspect of the present invention, there is provided a back pressure control method according to the first aspect, wherein when the packet length exceeds a preset threshold value of an individual back pressure counter, the packet is transmitted to a packet switch. It restricts input.

A back pressure control method according to a third aspect of the present invention is the back pressure control method according to the first or second aspect, wherein individual back pressure counters are provided corresponding to a plurality of transmission sources that input packets to the packet switch. is there.

A back pressure control method according to a fourth aspect of the present invention is the back pressure control method according to any one of the first to third aspects, wherein the packet is divided into a plurality of fixed-length pages, and the divided plurality of pages are divided. Is counted to count the packet length.

According to a fifth aspect of the present invention, there is provided a back pressure control method according to the fourth aspect, wherein a plurality of pages constituting a packet are transferred to a switch processing unit for outputting a plurality of pages to a predetermined destination. The page is stored in the packet memory, and after all the pages constituting the packet are stored in the packet memory, the pages are continuously transferred to the switch processing unit.

A back pressure control device according to a sixth aspect of the present invention is a back pressure control device of a packet switch for outputting an input packet to a predetermined destination, wherein the back pressure control device has a threshold and counts the packet length of the input packet. A pressure counter, and an individual back pressure counter that counts the packet length of the packet when the packet length counted by the shared back pressure counter exceeds the threshold value of the shared back pressure counter.

According to a seventh aspect of the present invention, there is provided the back pressure control device according to the sixth aspect, wherein a plurality of individual back pressure counters are provided corresponding to a plurality of transmission sources for inputting a packet to the packet switch. It is.

According to an eighth aspect of the present invention, there is provided a back pressure control device according to the sixth or seventh aspect, further comprising a reception processing unit for dividing a packet into a plurality of fixed-length pages, a shared back pressure counter, The individual back pressure counter counts a plurality of divided pages and counts a packet length.

A back pressure control device according to a ninth aspect of the present invention is the back pressure control device according to any one of the sixth to eighth aspects, wherein the switch processing unit outputs a plurality of pages constituting the packet to a predetermined destination. , A packet memory for storing a plurality of pages, and a packet memory management unit for continuously transferring the pages to the switch processing unit after all the pages constituting the packet are stored in the packet memory.

[0015]

Next, the configuration of a packet switch according to an embodiment of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram of a packet switch according to an embodiment of the present invention.

In FIG. 1, 1 is a packet switch,
The packet switch 1 includes input buffer processing units 40 to
The system includes a plurality of buffer processing units 30 to 35, each of which includes a set of an output buffer 45 and output buffers 50 to 55, and a switch processing unit 2 for communicating data between the plurality of buffer processing units 30 to 35. Also, the buffer processing units 30 to 35
Have packet input / output interfaces, and are connected to packet processing units 20 to 25 having various functions via these input / output interfaces.

The input buffer processing units 40 to 45 of the buffer processing units 30 to 35 are
5 through the packet input interface and the buffer processing unit 30 serving as the destination of the packet.
~ 35 destination numbers are transmitted. Further, the input buffer processing units 40 to 45 receiving the packet and the destination number
Divides the received packet into fixed-length packets of a plurality of pages, and transmits the divided packets to the switch processing unit 2 together with the destination number via the output interface.

Further, the switch processing unit 2 having received the fixed-length packet and the destination number converts the pages, which are a plurality of fixed-length packets, to the destination buffer processing unit 3 based on the destination number.
The packet is transferred to the output buffer processing units 50 to 55 of 0 to 35 via the input interface of the packet. Then, the output buffer processing units 50 to 55 receiving the plurality of pages,
The packet is reproduced from the received page, and the reproduced packet is transmitted to the packet processing units 20 to 25 via the packet output interface.

On the other hand, the output buffer processing units 50 to 55
Any one of a plurality of specific input buffer processing units 40 to
From 45, input restriction information is constantly output to the switch processing unit 2 in order to restrict the input of the packet, that is, perform the back pressure.

The switch processing unit 2 determines which of the input buffer processing units 40 to 45 should limit the packet based on the input input restriction information, and converts the input restriction information to a plurality of input buffer processing units. 40 to 45 are always output as output restriction information. Based on the output restriction information input from the switch processing unit 2, the input buffer processing units 40 to 45 restrict the transfer of pages to specific buffer processing units 30 to 35.

Next, the input buffer processing units 40 to 45 will be described in detail with reference to the block diagram shown in FIG.
Since the input buffer processing units 40 to 45 have the same configuration, only the input buffer processing unit 40 will be described.

The input buffer processing unit 40 includes a reception processing unit 60 connected to the packet processing unit 20 via an input interface. The reception processing unit 60 includes the page identification unit 6
2 and the read / write control unit 63 are connected.
Upon receiving the packet and the destination number of the packet from the corresponding packet processing unit 20, the reception processing unit 60 divides the packet into a plurality of pages of fixed length packets,
A plurality of pages and destination numbers, which are fixed-length packets, are output to the read / write control unit 63 and the page identification unit 62.

The page identification section 62 is connected to a packet memory management section 64 having a link list management section 66 and a free list management section 67, and a link header generation section 68. Then, the page identification unit 62 sends the page input notification output from the reception processing unit 60 to the read / write control unit 63 as the location information indicating which location of the packet contains the destination number as the location information indicating the location of the packet. At the same time, the data is output to the packet memory management unit 64 and the link header generation unit 68.

On the other hand, a packet memory 61 and a packet memory management unit 64 are connected to the read / write control unit 63, and are also connected to the switch processing unit 2 via an output interface. And lead /
The write control unit 63 receives a page from the reception processing unit 60, receives an address and a write control signal from the packet memory management unit 64, and writes and stores the received page in the packet memory 61. Further, the read / write control unit 63 receives a read control signal, an address, and a destination number from the packet memory management unit 64, reads out the page stored in the packet memory 61 by receiving these information, and reads the destination number and the page number. Are output to the switch control unit 2 via the output interface.

The packet memory management unit 64 is connected to a page identification unit 62, a read / write control unit 63, a link header generation unit 68, and a switch processing unit 2, and is also connected to a link memory 65. I have. Then, the packet memory management unit 64 controls the read / write control unit 63 to perform address management and timing control for reading and writing pages from / to the packet memory 61 by the read / write control unit 63. The address management of the packet memory 61 is performed by the packet memory management unit 6.
The link list management unit 66 and the free list management unit 67 constituting the management unit 4 manage using the link memory 65. Further, the packet memory management unit 64 monitors the link header generation unit 68 to determine whether or not there is a packet to be transmitted to the switch processing unit 2.
By reading the link header information from the link header generation unit 68 based on the output restriction information input from the, and notifying the read address to the read / write control unit 63,
A plurality of pages constituting a packet are transferred from the packet memory 61 to the switch processing unit 2.

When notified that a page has been input from the page identification section 62, the free list management section 67 reads one address for writing a page into the packet memory 61 from the free list, and reads this address. Deleted addresses from the free list. Here, the free list is a list in which free addresses of the packet memory 61 are arranged in order, and these addresses are stored in the link memory 65.

Further, the free list management section 67 outputs the read address to the read / write control section 63, the link list management section 66, and the link header generation section 68 as a write address.

On the other hand, when an address is input from the link list management unit 66, it is determined that the address is a free address, and the free list management unit 67 adds the address to the end of the free list and stores it in the link memory 65. I do.

The free list is generated at the time of initial setting of the input buffer control unit 40, and is stored so that all addresses of the packet memory 61 are one link.

That is, as shown in FIG. 3, the addresses a0 to an of the link memory 65 correspond to the addresses of the packet memory 61, a1 is stored at the position a0 of the link memory 65, and a2 is stored at the position of a1, and this storage is sequentially repeated to associate all addresses, thereby completing a free list arranged in the order of a0 to an. In order to identify the beginning and end of the free list, a free head pointer 91 and a free tail pointer 92 are provided, and a0 is stored in the free head pointer 91 and an is stored in the free tail pointer 92.

When the free list management section 67 outputs an address, as shown in FIG. 4, it outputs the address a0 stored in the free head pointer 91, and outputs the address a0 indicated by the free head pointer 91.
The address a1 stored at 0 is read, the address is stored in the free head pointer 91, and the address a0 is deleted from the free list.

When an address is output from the link list management section 66 to the free list management section 67, as shown in FIG. 5, the output address is an address that is not linked to the free list. That is, as shown in FIG. 4, since the address a0 is not linked to the free list, the address a0 is notified from the link list management unit 66. At this time, the free list management unit 67, as shown in FIG.
After writing the address an to the address an of the link memory 65 indicated by No. 2, the address a0 is also written to the free tail pointer 92, and the address a0 is added to the end of the free list.

As described above, the page is stored in the packet memory 61.
Is updated every time a page is read from the packet memory 61, and the free tail pointer 92 is updated each time a page is read from the packet memory 61.

The link list management unit 66 generates a link list for each packet from the address received from the free list management unit 67 and the page input notification received from the page identification unit 62. Here, the link list is a list in which the addresses output from the free list management unit 67 and the position information of the packets notified from the page identification unit 62 are arranged in the output order. The position information is the link memory 65
Saved in

When the link list management unit 66 receives the link header information from the link header generation unit 68,
By comparing the destination number of the packet specified therein with the output restriction information from the switch processing unit 2, it is determined whether the packet can be transferred. Further, the first position of the link list for the packet is confirmed from the address information included in the link header information. Then, from the link memory 65, the address where the page making up the packet is stored is read out, and these read addresses are sent to the read / write control unit 63 and the free list management unit 67 together with the destination number and the read control signal. Output.

When the link header generation unit 68 is notified by the page identification unit 62 that the first page constituting the packet has been input, the packet memory management unit 6
4 is stored in the link head pointer 93. When the link header generation unit 68 is notified that the last page constituting the packet has been input from the page identification unit 62,
The address information and the destination number of the link head pointer 93 are stored in the transmission queue for each destination as link header information. Then, the packet memory management unit 64 determines whether or not the link queue information is included in the transmission queue for each destination, and when recognizing that the link header information is included, the link Read the header information.

If the output is restricted for a specific destination number, the packet memory management unit 64 stores the link header information even if the transmission queue of the destination includes the link header information. Instead, the link header information is stored in the transmission queue, and the link header information included in the transmission queue for another destination is read. Further, if the transmission queue for the specific destination of the link header generation unit 68 is gone, the packet memory management unit 64
Does not control to write the page for this destination transferred from the reception processing unit to the packet memory 61. Therefore, the packet is discarded by the output restriction information without transferring the page to the switch processing unit 2.

That is, for example, a packet is composed of four pages, and a1, a3, a
When empty addresses of the packet memory 61 are provided in the order of 5, a7, when the first page of the packet is input, as shown in FIG. 6, the link list management unit 66 and the link header generation unit 68 Receives the address a1 from the free list management unit 67. At this time, the link header generation unit 68 stores the address a1 in the link head pointer 9
Save to 3. Further, the link list management unit 66 stores the address a1 in the link tail pointer 94 set therein, and sets a last bit indicating whether the page input to the address a1 of the link memory 65 is the last of the packet. Write as 0.

Next, when the next page of the same packet is input, as shown in FIG.
And the link header generation unit 68 include a free list management unit 67
Receives the address a3. At this time, the link header generator 68 ignores the address a3. Further, the link list management unit 66 stores the address a3 in the address a1 stored in the link tail pointer 94 of the link memory 65, and sets the last bit to 0 in the address a3.
And updates the link tail pointer 94 to the address a3. At this point, {a1, a3}
Is generated.

Similarly, when the address a5 is input, as shown in FIG. 8, the link tail pointer 94 is updated to the address a5, the address a5 is stored in the address a3, and the last bit is set to 0 in the address a5. Is written, and as a result, a link list of {a1, a3, a5} is generated.

When the last page of the packet is input, as shown in FIG. 9, the link list management unit 66 and the link header generation unit 68 make the free list management unit 67
Receives the address a7. At this time, the link header generation unit 68 ignores the address a7, but combines the address a1 stored as the value of the link header pointer 93 previously stored with the destination number as link header information and transmits the link header information for each internal destination. Save to queue. Further, the link list management unit 66 writes the address a7 in the address a5 stored in the link tail pointer 94 of the link memory 65, writes the last bit as 1 in the address a7, and stores the link tail pointer 94 in the address a.
Update to 7. At this point, {a1, a3, a5, a
A link list of 7 $ is generated.

When reading out the packets stored in the packet memory 61 as shown in FIGS.
As indicated by 0, the packet memory management unit 64 reads the address a1 from the link header information stored in the transmission queue from the link header generation unit 68, and stores this address a1 in the internal header pointer 95. And
The link list management unit 66 transfers the stored address a1 to the read / write control unit 63 and the free list management unit 67, transfers the page from the packet memory 61 to the switch processing unit 2, and transfers the address a1 of the link memory 65. When the state of the last bit is recognized as 0, the address a3 written here is taken out and the header pointer 95 is updated. At this point, the link list for this packet is {a3, a5, a7}.

Further, the link list management unit 66 similarly extracts the information of the address a3 stored in the header pointer 95 of the link memory 65, and
Read / write control unit 63 and free list management unit 67
When the page is transferred from the packet memory 61 to the switch processing unit 2 and the state of the last bit of the address a3 of the link memory 65 is recognized as 0, the address a5 written here is taken out.
The header pointer 95 is updated.

As described above, when the update of the header pointer 95 is repeated and the state of the last bit is recognized to be 1, the update of the header pointer 95 is stopped, and the above-described repetition operation is terminated. All the pages to be processed are transferred to the switch processing unit 2.

Next, the output buffer processing units 50 to 55 will be described in detail with reference to the block diagram shown in FIG. Since the output buffer processing units 50 to 55 have the same configuration, only the output buffer processing unit 50 will be described.

The output buffer processing unit 50 includes a page identification unit 70 and a read / write control unit 72 connected to the switch processing unit 2 via an output interface.

The page identification section 70 is connected to a packet memory management section 64 having a link list management section 66 and a free list management section 67, a counter control section 75, and a link header generation section 78. . Then, the page identification unit 70 determines the read / write control unit 72 from the page output from the switch processing unit 2 and the transmission source number.
The input notification of the page output to the packet memory management unit 73, the counter control unit 75, and the link header generation unit 78 as the position information and the transmission source number indicating which position of the packet this page contains. Output.

On the other hand, the read / write control section 72 is connected to a packet memory 71, a packet memory management section 73, and a transmission processing section 79. When the read / write control unit 72 inputs a page from the switch processing unit 2 and inputs an address and a write control signal from the packet memory management unit 73, the read / write control unit 72 writes the page input from the switch processing unit 2 into the packet memory 71. To save. Further, when the read control signal and the address are input from the packet memory management unit 73, the packet memory 71
, And outputs the read page to the transmission processing unit 79.

The packet memory management section 73 includes a page identification section 70, a read / write control section 72, a link header generation section 78, a link memory 77, a transmission processing section 79, and an account memory connected to the counter control section 75. 76 is connected. Then, the packet memory management unit 73 controls the read / write control unit 72 for address management and timing control for reading and writing pages to and from the packet memory 71 by the read / write control unit 72. The address management of the packet memory 71 is managed by a link list management unit 80 and a free list management unit 81 constituting the packet memory management unit 73 using a link memory 77. The packet memory management unit 73 receives the link header information from the transmission processing unit 79 to transfer the plurality of pages constituting the packet to the transmission processing unit 79, and reads out the plurality of pages from the packet memory 71. Timing control. Further, the packet memory management unit 73 outputs the address output to the read / write control unit 72 to the account memory 76 in order to provide a correlation between the back pressure function and the address management of the packet memory 71. This control signal is output to the counter control unit 7.

When the free list management unit 81 is notified that a page has been input from the page identification unit 70 by the same operation as the free list management unit 67 provided in the input buffer processing unit 40, Packet memory 7
One address for writing a page to 1 is read from the free list, and the read address is deleted from the free list. Here, the free list is
A list in which free addresses of the packet memory 71 are arranged in order, and these addresses are stored in the link memory 77.

Further, free list management section 81 outputs the read address to read / write control section 72, link list management section 80, link header generation section 78, and account memory 76 as a write address.

On the other hand, when an address is input from the link list management unit 80, it is determined that the address is a free address, and the free list management unit 81 adds the address to the end of the free list and stores it in the link memory 77. I do.

The free list is generated at the time of initial setting, as in the case of the input buffer control unit 40 shown in FIGS. 3 to 5, and is stored so that all addresses of the packet memory 71 become one link. You. The method of storing this address in the link memory 77 is based on the input buffer processor 40.
Therefore, the description is omitted.

Then, like the input buffer processing unit 40, the link list management unit 80 includes a free list management unit 81.
A link list is generated for each packet based on the address received from the server and the page input notification received from the page identification unit 70. Here, the link list is a list in which the addresses output from the free list management unit 81 and the position information of the packets notified from the page identification unit 70 are arranged in the output order. The position information is stored in the link memory 77.

Upon receiving the link header information from the transmission processing unit 79, the link list management unit 80 recognizes the first position of the link list for the packet from the address information contained therein. Then, the address at which the page making up the packet is stored is read out from the link memory 77, and is output to the read / write control unit 72, the free list management unit 81, and the account memory 76 as these read addresses.

Further, when the link header generation unit 78 is notified from the page identification unit 70 that the first page constituting the packet has been input, the packet memory management unit 7
3 is stored in the link head pointer 93 for each transmission source number.
Further, upon being notified from the page identification section 70 that the last page constituting the packet has been input, the link header generation section 78 uses the address information stored in the link head pointer 93 as link header information as the transmission processing section. 79
Output to

Here, this link list generation method is as follows.
Since it is the same as the input buffer processing unit 40, the description is omitted. The difference from the input buffer processing unit 40 is that when reading a page from the packet memory 71, the input buffer processing unit 40 receives the link header information from the link header generation unit 68 while the output buffer processing unit 50
Is a point input from the transmission processing unit 79, the switch processing unit 2
Since the pages are randomly input from the plurality of input buffer processing units 40 to 45, the link head pointers 93 and link tail pointers 94 used for generating the link list are required for the number of input buffer processing units 40 to 45. This is the point.

The counter control unit 75 is connected to a back pressure counter 74. The back pressure counter 74 has a shared back pressure counter and an individual back pressure counter for each transmission source number. Then, according to an instruction from the counter control unit 75, the count value of each of the shared back pressure counter and the individual back pressure counter is incremented or decremented. Further, a threshold value for the count value is set in advance for each of the shared backpressure counter and the individual backpressure counter, and when the count value exceeds the threshold value, the counter monitoring unit is notified of the situation.

The counter control unit 75 selects a back pressure counter to be incremented every time a page is notified from the page identification unit 70, and increments the back pressure counter by a counter value. Instruct the pressure counter 74. Further, when a page is written to the packet memory 71, the number of the selected back pressure counter is written to the account memory 76 for the address input from the packet memory management unit 73.

When the reading of the page of the packet memory 71 is instructed from the packet memory management unit 73, the counter control unit 75 stores the address input from the packet memory management unit 73 in the account memory 76. The number of the back pressure counter is read out, and the back pressure counter 74 is instructed to decrement the count value of the back pressure counter indicated by the number.

The back pressure counter selected by the counter control unit 75 when a page is input first selects the shared back pressure counter regardless of the source of the page. If it is notified that the count value of the shared back pressure counter has exceeded the set threshold value, the individual back pressure counter of the source of the input page is selected. Then, when notified that the count value of the individual back pressure counter exceeds the set threshold value, the counter control unit 75 sets the input limit to the source for the individual back pressure counter so as to limit the input. The information is output to the switch processing unit 2.

Here, the addresses of the link memory 77 and the account memory 76 match the addresses of the packet memory 71. That is, as shown in FIGS. 12 and 13, for example, the address a0 indicates the address of the packet memory 71 in which one page is stored, and the link memory 77 and the account memory 76 store additional information for the page. Points to the stored address. The additional information refers to the address information of the next page to which the page specified by the address a0 is related in the link memory 77, and the page specified by the address a0 is used for storing the packet in the account memory 76. If so, it indicates the number of the back pressure counter that counted the page. FIG.
In No. 2, since no page has been input, only a free list managed by the free list management unit 81 is generated in the link memory 77. The address a0 is set in the free head pointer 91 indicating the beginning of the free list, the address a11 is set in the free tail pointer 92 indicating the end of the free list, and all addresses of the link memory 77, that is, the packet memory 71 are set.
Are associated as one link. Therefore, for example, the page of the packet memory 71 indicated by the address a0 is treated as a free page because it is not used for storing the packet, and the link memory 77 stores the address of the page related to the page. The address a1 is stored, and the data indicated by the address is treated as invalid data in the account memory 76 because the page is not used for storing the packet.

Here, for example, when a packet composed of five pages is input to the output buffer processing unit 50, as shown in FIG. The management unit 81 assigns addresses a0, a1, a2, a3, a4 from the free list.
And take it out. These addresses are used as write addresses for storing the page in the packet memory 71, and the free head pointer 91 is updated to the address a5. The packet memory 71 stores five pages at the extracted address. Then, the link memory management unit 80 uses the link tail pointer 94 to generate a link list of the address where the page is stored. The link header generator 78 sets the address a0 to the link head pointer 93, and the account memory 76 stores the counter number 0 of the shared back pressure counter at the address used for the link list.

Then, when the link header information is input from the link header generation unit 78, the transmission processing unit 79 manages the link header information to read out the packet from the packet memory 71 in accordance with the internal processing status. Output to the unit 73. Thereafter, the packets are reassembled from the plurality of pages input from the packet memory 71 and output to the packet processing unit 20.

Next, the operation of the above embodiment will be described.

First, the input buffer processing unit 4 receiving the packet and its destination number from the packet processing units 20 to 25
0 to 45 are divided into fixed packets of a plurality of pages in the internal reception processing unit 60 and transmitted to the read / write control unit 63 and the page identification unit 62.

Then, page identification section 62 informs link header generation section 68 and packet memory management section 64 that the page has been input. Further, the packet memory management unit 64 notifies the read / write control unit 63 of an empty address of the packet memory 61 in order to store the page in the packet memory 61. Then, the read / write control unit 63 writes the received page to an address supplied from the packet memory management unit 64.

This operation is repeated for all pages input to the read / write control unit 63.
The packet memory management unit 64 saves the address of the packet memory 61 on which the page constituting the packet is written in the link memory 65 as a link list, and the link header generation unit 68 writes the first page constituting the packet. Record the address. When the last page of the packet is written, the link header generation unit 68 stores the address of the first page of the packet as link header information in a transmission queue prepared for each destination.

Further, the packet memory management unit 64 monitors the transmission queue of the link header generation unit 68, and when link packet information is found therein, saves it in the link memory 65 from the address recorded in the link header information. The first address of the linked list, that is, the address of the first page of the packet stored in the packet memory 61 is recognized. Then, in order to read all the pages of the packet from the packet memory 61 using this address, the address of the packet memory 61 in which the page constituting the packet is written is taken out from the link memory 65 in the order of the link list, This is supplied to the read / write control unit 63 together with the destination number.

Further, in the read / write control unit 63,
The page is read from the packet memory 61 and this page is supplied to the switch processing unit 2 together with the destination number. During this time, the address used for reading is again managed as an empty address in the packet memory 61 by the packet memory management unit 64, and can be reused when another packet is input.

As described above, the input buffer processing units 40 to 4
In 5, the packet is supplied to the switch processing unit 2 after all pages constituting the packet are once stored in the packet memory 61. Further, the write processing and the read processing of the packet memory 61 are executed alternately, so that both operations can be executed independently.

Further, the switch processing unit 2 which has received the page and the destination number from the input buffer processing units 40 to 45 outputs the output buffer processing unit 5 as the destination from the destination number.
0 to 55, and outputs the received page and the transmission source number capable of identifying the input buffer processing units 40 to 45 that output the page to the determined output buffer processing units 50 to 55. .

Then, the output buffer processing units 50 to 55 which input the page and the transmission source number from the switch processing unit 2
The read / write control unit 72 and the page identification unit 7
Tell 0. Thereafter, the page identification unit 70 notifies the link header generation unit 78, the counter control unit 75, and the packet memory management unit 73 that the page has been input. Further, the packet memory management unit 73 notifies the read / write control unit 72 of a free address of the packet memory 71 in order to store the page in the packet memory 71.
Then, the read / write control unit 72 writes the input page to the address supplied from the packet memory management unit 73.

This operation is executed for each transmission source number so as to correspond to the page input from the plurality of input buffer processing units 40 to 45, and to execute the operation for all the pages input to the read / write control unit 72. Is repeated. In the meantime, the packet memory management unit 73 stores the address of the packet memory 71 in which the page constituting the packet is written in the link memory 77 as a link list, and the link header generation unit 78 stores the first page constituting the packet. Record the address where was written.

The counter control unit 75 designates a counter provided in the back pressure counter 74 for counting the number of input pages, increments the count value, and uses the account memory 76 to execute the packet memory operation. The number of the back pressure counter that specifies the increment of the count value is stored in association with the address of the page stored in 71.
Then, when the last page constituting the packet is written, the link header generation unit 68 uses the address of the first page of the packet as link header information as the transmission processing unit 79.
To supply.

Further, the transmission processing unit 79, which has received the link header information from the link header generation unit 78, reads the link header information from the packet memory 71 in accordance with the internal processing status so as to read the packet from the packet memory management unit. 73. Then, when the packet memory processing unit 73 receives the link header information, the link memory 77 starts from the address recorded in the link header information.
Of the link list stored in the packet memory 71, that is, the address of the first page of the packet stored in the packet memory 71. The link memory 77 is used to read all the pages making up the packet from the packet memory 71 using this address.
, The address of the packet memory 71 in which the page constituting the packet is written is taken out according to the order of the link list, and supplied to the read / write control unit 72.

The read / write control unit 72 reads a page from the packet memory 71 at this address and supplies it to the transmission processing unit 79. This operation is 1
The process is repeated until all addresses associated with the link list are extracted for one packet. During this time, the address used for reading is again stored in the packet memory 61 in the packet memory management unit 64.
Is managed as a free address, and can be reused when another packet is input.

On the other hand, the counter control unit 75 stores the counter number associated with the address used for reading when the page was saved before, in the account memory 76.
And instructs the back pressure counter 74 to decrement the count value of the back pressure counter 74 for that counter number.

Then, the transmission processing unit 79, which has received the page from the read / write control unit 72, reassembles the packet and supplies it to the packet processing units 20 to 25.

As described above, the output buffer processing units 50 to 5
5 indicates that after all the pages constituting the packet are once stored in the packet memory 71, the packet processing units 20 to 25
To supply the packet. Further, the write operation and the read operation of the packet memory 71 are executed alternately, so that both operations can be executed independently.

Then, the back pressure counter 74
Prepares a shared back pressure counter and individual back pressure counters corresponding to the plurality of input buffer processing units 40 to 45. In addition, each counter sets a threshold value for the count value in advance, and when the count value exceeds the threshold value, notifies the counter monitoring unit 75 of the situation. Here, the threshold to be set is
It is restricted in the following relations.

PM1max> BP0 + SUM (BPn) (n = 1 to N) (1) BP0 + BPn> PSmax (2) PMmax: Maximum number of stored pages in the packet memory BP0: Threshold of the shared back pressure counter BPn: Individual back Pressure counter threshold PSmax: Number of pages considering the maximum rate of pages input from one transmission source n: Individual back pressure counter number N: Total number of output buffer processing units

Therefore, the capacity of the packet memory 71 can be reduced as compared with the case where only an individual back pressure counter is prepared for each transmission source. That is, in the above embodiment, the threshold value of each individual back pressure counter can be made smaller than that of a case where only an individual back pressure counter is prepared. As described above, when only the individual back pressure counter is prepared, the threshold value is determined in consideration of the maximum rate of the packet input from one transmission source, so that the threshold value of the individual back pressure counter needs to be increased. . This inevitably causes the packet memory 71 to be large. That is, when only an individual back pressure counter is prepared, the following relationship is obtained.

PMmax> SUM (BPn) (n = 1 to N) (3) BPn> PSmax (4)

As described above, the shared back pressure counter is prepared, and the threshold value is shared by the individual back pressure counters, so that the threshold value of the individual back pressure counter can be kept low. In other words, the capacity of the packet memory 71 can be reduced because the total threshold value is small.

When a page is input, the counter control unit 75 first selects a shared back pressure counter regardless of the input buffer processing units 40 to 45 that output the page. Therefore, when the amount of pages input to the output buffer processing units 50 to 55 is small, the pages are mostly counted by this shared back pressure counter.

If the count value of the shared back pressure counter exceeds the set threshold value,
For the page input at that time, an individual back pressure counter prepared for the input buffer processing units 40 to 45 that output the page is selected, and the number of pages is counted. Further, when the count value of the individual back pressure counter exceeds the set threshold value, the counter control unit 75 limits the input to the input buffer processing units 40 to 45 corresponding to the individual back pressure counter. Then, the input restriction information is supplied to the switch processing unit 2.

The switch processing section 2 outputs the output restriction information to the input buffer processing sections 40 to 45 which have received the input restriction from the output buffer processing sections 50 to 55. The input buffer processing units 40 to 4 receiving the output restriction information
5 is an output buffer processing unit 50 for instructing output restriction.
Even if the link header information is stored in the transmission queue addressed to .about.55, no reading is performed. That is, the page is not transferred to the output buffer processing units 50 to 55 instructing the output restriction. Therefore, this operation enables back pressure at the packet level.

The output buffer processing units 50 to 55
Since the page is always read after one packet page is accumulated from the packet memory 71, the counter control unit 75 may use different counters for counting a plurality of pages constituting one packet. is there. However, since the link list manages the address where the page is stored and is not related to the count value of the back pressure counter, the packet memory 71
It does not affect the reading of the page from.

Further, it is possible to generate a situation where the count value of the individual back pressure counter exceeds the threshold value even though the count value of the shared back pressure counter is lower than the threshold value. This is because the back pressure is continued until the packet that caused the back pressure is read from the packet memory 71 and processed, and the processing of the page input from the other input buffer processing units 40 to 45 is performed. The effect can be kept low.

[0092]

According to the present invention, since a page obtained by dividing an input packet is counted by two types, a shared back pressure counter and an individual back pressure counter corresponding to the packet memory of the transmission source, the shared back pressure counter is used. Since the threshold value of the individual back pressure counter is shared by the individual back pressure counters, the threshold value of the individual back pressure counter can be set lower, the total of the threshold values can be set smaller, and the capacity of the packet memory can be set lower, so that the packet A pressure function is obtained.

A back pressure counter is composed of a shared back pressure counter and an individual back pressure counter corresponding to the transmission source. Normally, counting is performed using the shared back pressure counter. Even if a long packet is input, it can cope with continuously arriving pages, and a back pressure function can be obtained even with a relatively small packet memory.

Then, after once storing the packet in the packet memory, it is determined whether or not to transfer a plurality of pages constituting the packet to the output side.

Further, since an individual back pressure counter is provided on the output side in correspondence with the packet memory on the input side, back pressure can be executed on a packet from a specific packet memory on the input side.

Also, a packet is divided as a fixed length packet called a page, and the packet switch can be inputted in a page unit from a plurality of input sides instead of a packet unit input on the output side. Packets can be input simultaneously from a plurality of input sides without occupying a switch by a long packet, so that back pressure in units of packets can be achieved by high-speed packet switching.

[Brief reading of drawings]

FIG. 1 is a block diagram of a packet switch according to an embodiment of the present invention.

FIG. 2 is a block diagram illustrating a configuration of an input buffer processing unit according to the embodiment.

FIG. 3 is an explanatory diagram showing a situation where all addresses in the input buffer processing unit are stored as one link.

FIG. 4 is an explanatory diagram showing a situation where all addresses in the input buffer processing unit are stored as one link.

FIG. 5 is an explanatory diagram showing a situation in which all addresses in the input buffer processing unit are stored as one link.

FIG. 6 is an explanatory diagram showing a generation state of a link list in the input buffer processing unit of the embodiment.

FIG. 7 is an explanatory diagram showing a generation state of a link list in the input buffer processing unit of the embodiment.

FIG. 8 is an explanatory diagram showing a state of generating a link list in the input buffer processing unit of the embodiment.

FIG. 9 is an explanatory diagram showing a generation state of a link list in the input buffer processing unit.

FIG. 10 is an explanatory diagram showing a status of a link list when packets stored in a packet memory in the input buffer processing unit are read out.

FIG. 11 is a block diagram illustrating a configuration of an output buffer processing unit according to the embodiment.

FIG. 12 is a link memory in the output buffer processing unit,
FIG. 3 is an explanatory diagram showing a relationship between an account memory and a packet memory.

FIG. 13 is an explanatory diagram showing a situation when a packet is input to the output buffer processing unit.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Packet switch 2 Switch processing part 20-25 Packet processing part 30-35 Buffer processing part 40-45 Input buffer processing part 50-55 Output buffer processing part 60 Reception processing part 61, 71 Packet memory 62, 70 Page processing part 63, 72 read / write control unit 64, 73 packet memory management unit 65, 77 link memory 66, 80 link list management unit 67, 81 free list management unit 68, 78 link header generation unit 74 back pressure counter 75 counter control unit 76 account memory 79 Transmission processing unit 91 Free head pointer 92 Free tail pointer 93 Link head pointer 94 Link tail pointer 95 Header pointer

Continuation of the front page (58) Field surveyed (Int.Cl. ⁷ , DB name) H04L 12/56 H04L 12/28

Claims (9)

(57) [Claims] 1. A back pressure control method for a packet switch for outputting an input packet to a predetermined destination, wherein a packet length of the input packet is counted based on a threshold set in advance by a shared back pressure counter. When the packet length counted by the shared back pressure counter exceeds the threshold value of the shared back pressure counter, the packet length is counted based on a preset threshold value by the individual back pressure counter. Back pressure control method. 2. The back pressure control method according to claim 1, wherein when the packet length exceeds a preset threshold value of the individual back pressure counter, input of a packet to the packet switch is restricted. 3. The back pressure control method according to claim 1, wherein an individual back pressure counter is provided for each of a plurality of transmission sources that input packets to the packet switch. 4. A dividing a packet into a plurality of fixed length pages back according to any one of claims 1 to 3, characterized in that counting the packet length and counts the plurality of pages this division Pressure control method. 5. When transferring a plurality of pages constituting a packet to a switch processing unit for outputting the page to a predetermined destination, the plurality of pages are saved in a packet memory, and all the pages constituting the packet are saved in the packet memory. 5. The back pressure control method according to claim 4, wherein the pages are continuously transferred to the switch processing unit after the switching. 6. A back pressure control device of a packet switch for outputting an input packet to a predetermined destination, comprising: a shared back pressure counter having a threshold value for counting the packet length of the input packet; A back pressure control device comprising: an individual back pressure counter that counts a packet length of a packet when a packet length counted by the shared back pressure counter exceeds a threshold value of the shared back pressure counter. 7. The back pressure control device according to claim 6, wherein a plurality of individual back pressure counters are provided corresponding to a plurality of transmission sources that input packets to the packet switch. 8. A reception processing unit for dividing a packet into a plurality of fixed-length pages, wherein the shared back pressure counter and the individual back pressure counter count the plurality of divided pages and count the packet length. 7. The method according to claim 6, wherein
Or the back pressure control device according to 7. 9. A switch processing unit for outputting a plurality of pages constituting a packet to a predetermined destination, a packet memory for storing a plurality of pages, and a switch after all pages constituting the packet are stored in the packet memory. The back pressure control device according to any one of claims 6 to 8, further comprising a packet memory management unit that continuously transfers pages to the processing unit.