Packet switch

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Technical field to which the invention belongs]

The present invention relates to a packet switch applied as a node device in a variable-length packet communication network. More specifically, a common buffer-type variable-length packet switch using a common buffer memory as a memory for temporarily storing received packets. Regarding.

【0002】

[Conventional technology]

In the Internet Protocol (hereinafter referred to as IP), which has been attracting attention in recent years, message transfer is performed using a variable length packet (IP packet) called an IP datagram as a transfer unit. In the conventional node device that composes the IP packet network, the received packet is switched to the destination route by software processing, but a fixed-length packet (data) is used in the node device due to a request for high-speed switching. A device configuration for switching with a block) as a transfer unit has been proposed.

【0003】

As a node device that transfers IP packets at high speed, for example, in the paper "A 50-Gb / s IP Router" (Craig Partridge et al., IEEE / ACM TRANSACTIONS ON NETWORKING, Vol.6, No.3, June 1998) Each has multiple line cards (boards) that support multiple network interfaces and a Forwarding Engine card that has a routing table, for example, a point-to-point type typified by a crossover switch. Combined with a switch, each line card sends a data block containing the header part of the received packet to the transfer engine, and returns the data block containing the new header information updated by the transfer engine to the line card on the packet input side. However, a router device has been proposed in which each line card on the input side transfers the data block including the new header information and the rest of the packet to the line card on the output side.

【0004】

According to the above paper, each line card on the input side disassembles the packet into a chained page (data block) of 64 bytes and sends it, and each line card on the output side represents these pages as a packet. Assembled into a linked list, passed the assembled packet to a QoS processor, and disclosed that the QoS processor puts the packet in an appropriate position in the transmit queue based on the packet length, destination, and flow identifier specified by the forwarding engine. Has been done.

【0005】

An ATM (Asynchronous Transfer Mode) switch is an example of a switching device in which a packet transfer unit has a fixed length. In the ATM switch, after the 53-byte fixed-length packet (ATM cell) received from each input line is temporarily stored in the buffer memory, the stored cell is specified by the connection identification information (VPI / VCI) included in the cell header. It is routing to the output line of.

【0006】

If a common buffer type structure in which a buffer memory is shared by a plurality of input lines is adopted in the ATM switch, a variable length queue can be formed for each output line in the buffer memory. Therefore, for example, a cell sequence heading to the same output line. Even if is received from multiple input lines at the same time, as long as there is free space in the common buffer as a whole, it is possible to buffer the received cells from each input line without discarding them, effectively using memory resources. A switch can be realized.

【0007】

Japanese Unexamined Patent Publication No. 11-261584 proposes a switching device for variable-length messages that takes advantage of the above-mentioned common buffer memory. In the above-mentioned prior art, the common buffer memory is divided into a plurality of memory blocks corresponding to messages, one memory block in a free state is allocated to each received message, and a plurality of fixed-length messages received from each input line are allocated. It is divided into cells, and cells belonging to the same message are sequentially stored in the same memory block.

【0008】

[Problems to be Solved by the Invention]

In the router device described in the above-mentioned IEEE document, the input side line card negotiates with the output side line card via the switch allocator prior to the transmission of each packet, and the output side card accepts the packet reception. If this happens, transmission is started, so there is a problem with the packet switching processing speed. In addition, each line card on the input side needs a buffer for waiting for packets, and each line card on the output side also needs a buffer for packet assembly, so there is a problem in the efficiency of using the buffer memory. ..

【0009】

On the other hand, in the switching device described in JP-A-11-261584, when the last part of each message is input, all the cells stored in the memory block corresponding to the received message are stored in another memory area ( Since it is configured to be moved to the message queue), there is a problem in the time required to transfer the message between the memory areas and the efficiency of using the buffer memory.

【0010】

An object of the present invention is to provide a packet switch capable of high-speed switching of variable-length packets by efficiently utilizing a common buffer memory.

【0011】

[Means for solving problems]

In order to achieve the above object, the packet switch of the present invention is a common buffer memory shared by a plurality of input lines and a common buffer memory in which received packets from each input line are multiplexed in units of fixed-length data blocks. It is composed of the multiplexing means supplied to the above and the buffer control means for controlling the writing and reading of each of the fixed-length data blocks to the common buffer memory, and the buffer controlling means is each fixed output from the multiplexing means. When writing a long data block to the common buffer, an input queue for each variable length packet is formed, and when the final data block of the variable length packet is registered in the input queue, the input queue is used as the transfer destination of the variable length packet. It is characterized by linking to the output queue corresponding to the output line.

【0012】

More specifically, the buffer control means forms a plurality of input queues by linking the write addresses of each fixed-length data block in the common buffer memory for each variable-length packet, and the last fixed-length data of the variable-length packet. The first control means for linking the input queue whose block has already been written to the common buffer memory to the output queue corresponding to the transfer destination output line and the plurality of output queues formed corresponding to the output line are accessed in a predetermined order. A second control means for reading a fixed-length data block from the common buffer memory based on the linked address indicated by each output queue is provided. The input queue for each variable-length packet writes, for example, each fixed-length data block to the common buffer memory based on the write address fetched from the free address memory, and corresponds to each write address in the same variable-length packet. It is formed by storing the write address of the fixed-length data block of.

【0013】

In the present invention, each output queue is composed of an address table that stores, for example, a next read address indicating a data block to be read next and a final read address indicating the last data block, and the first control means is variable. By moving the write address of the first data block and the write address of the last data block of the long packet to the next read address and the last read address of the address table corresponding to the transfer destination output line, the input queue link to the output queue described above is made. Complete. In this case, the second control means reads the fixed-length data block and the address of the next fixed-length data block from the common buffer memory and the next-address memory, respectively, based on the next read address registered in each output queue. By using the address read from the next address memory as a new next read address in the output queue, it is possible to read the data blocks constituting each variable length packet one after another.

【0014】

When linking the input queue of the subsequent variable length packet to the output queue in which the final read address of the preceding variable length packet has already been registered, the first control means performs the subsequent variable length in the next address memory. The write address of the first data block of the packet may be linked to the last read address.

【0015】

BEST MODE FOR CARRYING OUT THE INVENTION

Hereinafter, examples of the present invention will be described in detail with reference to the drawings. FIG. 1 is a block diagram showing an embodiment of a packet switch according to the present invention. The packet switch 1 divides the variable length packet 100 input from the input lines LI-1 to LI-n into a plurality of fixed-length data blocks 110, and outputs a plurality of data blocks by adding an internal header 110A to each data block. Input line interfaces 10-1 to 10-n, a multiplexing unit 21 that time-divides the data blocks input from the input line interfaces 10-1 to 10-n and outputs them to the signal line L21, and the above signals. A common buffer memory 22 connected to the line L21, and a separation unit 23 that sequentially distributes the data block read from the common buffer memory 22 to the signal line L22 to a plurality of output line interfaces 20-1 to 20-n. A buffer control unit 30 that controls writing and reading of data blocks to the common buffer memory 22, an input counter 24 that counts the clock CLK0 indicating the writing cycle and generates an input line selection signal, and a clock CLK1 indicating the reading cycle. It consists of an output counter 25 that counts and generates an output line selection signal.

【0016】

The variable-length packet input from each input line LI-i (i = 1 to n) consists of a packet header 100A including a destination address and a data unit 100B. Each input line interface 10-i (i = 1 to n) divides the variable length packet 100 received from the input line LI-i into a plurality of fixed-length data blocks 110, for example, an input line number and a packet header. An internal header 110A including an output line number determined by the destination address extracted from 100A and block position display information indicating whether each data block 110 corresponds to the first block, the middle block, or the last block in the variable length packet. Generate, add this to each data block and output.

【0017】

Writing and reading of data blocks to the common buffer memory 22 alternates according to clocks CLK0 and CLK1. The multiplexing unit 21 cyclically selects the input line interfaces 10-1 to 10-n according to the input line selection signal generated on the signal line L24 by the input counter 24, and the data output from each input line interface. Block 110 is sequentially multiplexed on the signal line L21. On the other hand, the separation unit 23 specifies the data block read from the common buffer memory 22 to the signal line L22 by the output line interface 20-j (j) in which the output counter 25 is specified by the output line selection signal generated in the signal line L25. = 1 ~ n). The output line interfaces 20-1 to 20-n remove the internal header 110A from the data block 110 received from the separation unit 23, and send the data to the corresponding output lines LO-1 to LO-n.

【0018】

The buffer control unit 30 writes a data block to the common buffer memory 22 while forming a linked address list corresponding to the input line number i indicated by the internal header 110A appearing on the signal line L21 in each write cycle indicated by the clock CLK0. .. As will be described later, the buffer control unit 30 forms a new input queue corresponding to the input line each time the first block of the received packet appears on the signal line L21, and inputs the data of the subsequent intermediate block and the final block to the input line. Registered one after another in the corresponding input queue, and when the final block of the received packet is written to the common buffer memory 22, the input queue is linked so as to be linked to the output queue corresponding to the transfer destination output line of the received packet. -Dynamic control of the address list.

【0019】

The reading of the data block from the common buffer memory 22 is performed based on the output queue address list formed corresponding to each output line. The buffer control unit 30 checks the output queue corresponding to the output line selection signal given by the signal line L25 for the presence or absence of a data block to be read, and if the data block address is linked to the output queue, outputs the output queue. The next read address registered in the queue address list is used as the read address RA, one data block is read from the common buffer memory 22 to the signal line L22, and the next read address in the address list is the next data block address in the linked address list. Rewrite to.

【0020】

FIG. 2 is a block diagram showing details of the buffer control unit 30. The buffer control unit 30 includes a header analysis unit 31, an input queue control unit 32, an output queue control unit 33, a next address management unit 34, and an empty address memory (FIFO) for storing a free address of the common buffer memory 20. ) It consists of 35.

【0021】

The header analysis unit 31 analyzes the internal header of each data block appearing on the signal line L21, and determines whether the input line number IN-i, the output line number OUT-j, and the input data block are the first block of the received packet. The first display flag signal FP indicating the above and the final display flag signal EP indicating whether or not the input data block is the final block of the received packet are generated.

【0022】

The input queue control unit 32 has the address (packet start address: BAi (i = 1 to n)) 301 of the first data block registered in the input queue and the latest data block registered in the input queue for each input line. It has an input queue address table 300 indicating the address (latest address: WAi (i = 1 to n)) 302 of.

【0023】

The output queue control unit 33 has the read address (next read address RAj (j = 1 to n)) 311 of the data block located at the beginning of the output queue and the data block located at the end of the output queue for each output line. An output queue address table 310 indicating the read address (final read address EAj (j = 1 to n)) 312 and the queue flag (Fj (j = 1 to n)) 313 indicating the presence or absence of registered data in the output queue. I have.

【0024】

The secondary address management unit 34 includes a secondary address memory 340 composed of a plurality of address storage areas NA1 to NAm equal to the number of data blocks m that can be stored in the common buffer memory 22. Each storage area of the next address memory 340 is used to form a linked address list for reading the data block strings registered in the input queue in the order of registration.

【0025】

Hereinafter, assuming that a variable-length packet from the input lines LI-1 and LI-2 to the same output line LO-3 is input, the packet head address BA1 and the packet head address BA1 of the input queue corresponding to the input line LI-1 and The latest address WA1, the packet start address BA2 and the latest address WA2 of the input queue corresponding to the input line LI-2, the queue flag F3 of the output queue corresponding to the output line LO-2, the next read address RA3, and the last read address EA3. The function of the buffer control unit 30 will be described in detail with reference to FIGS. 2 and 3 to 5.

【0026】

The header analysis unit 31 analyzes the internal header 110A of each data block output to the signal line L21, and generates an input line number IN-i and an output line number OUT-i. If the data block is the first block of the variable length packet, the head display flag signal FP is turned on, and if it is the last block, the final display flag signal EP is turned on.

【0027】

The data block output to the signal line L21 is written to the common buffer memory 20 with the free address taken out from the free address FIFO 35 as the write address WA. At this time, the input queue control unit 32 updates the input queue address table 300 according to the status of the input line number IN-i output from the header analysis unit 31 and the head display flag signal FP. If the start display flag signal FP is on, the write address WA fetched from the free address FIFO35 is written to the packet start address BAi and the latest address WAi of the table entry corresponding to the above input line number IN-i. If the head display flag signal FP is off, the above write address WA is written to the latest address WAi. When a new address WA is written to the input queue address table 300, the address previously stored as the latest address WAi is output to the next address management unit 34. The next address management unit 34 stores the new write address WA fetched from the free address FIFO 35 in the storage area NAi corresponding to the address WAi.

【0028】

As a result, every time a fixed-length data block divided from one variable-length packet is written to the common buffer memory 22, the write address of the data block is stored in the next address memory 340, and the latest address WAi is updated. Ultimately, the packet start address BAi points to the address of the start data block of the variable length packet, and the latest address WAi points to the address of the last data block of the variable length packet.

【0029】

Figure 3 shows the data blocks D1-1 to D1-4 output from the input line interface 10-1 and the data blocks D2-1 to D2-2 output from the input line interface 10-2 to the common buffer memory 22. Indicates the state of the input queue address table 300 at the time when is written. Here, WA1-1 to WA1-4 are the values of the write address WA of the data blocks D1-1 to D1-4 obtained from the free address FIFO35, and WA2-1 to WA2-2 are the data blocks D2-1 to D2. Indicates the value of the write address WA of -2. In addition, RA3, EA3, and F3 contain the contents of the output queue address table entry 310-3 corresponding to the transfer destination output line LO-3 of the above data blocks D1-1 to D1-4 and D2-1 to D2-2. Shown.

【0030】

In the input queue address table corresponding to the input line LI-1, the write address WA1-1 of the start data block D1-1 is stored as the packet start address BA1, and the contents of the latest address WA1 are updated each time the data block is written. Then, it changes to WA1-1, WA1-2, WA1-3, WA1-4. In the next address memory 340, as shown in FIG. 3, the write addresses of the next data blocks are stored one after another in the storage area corresponding to the latest address WA1, and the packet start address BA1 and the next address memory of the input queue address table 300 are stored. With 340, a linked address list for each input line is formed.

【0031】

For example, by accessing the common buffer memory 22 and the secondary address memory 340 based on the address WA1-1 indicated by the packet leading address BA1, the leading data block D1-1 and the address WA1-2 of the next data block D1-2 are accessed. By using this address WA1-2 as the read address RA in the next read cycle, the next data block D1-2 and the address WA1-3 of the next data block D1-3 can be read. By repeating the same operation, it is possible to read all the data blocks registered in the input queue.

【0032】

Similar to the input line LI-1, in the input queue address table corresponding to the input line LI-2, the write address WA2-1 of the start data block D2-1 is stored as the packet start address BA2, and the contents of the latest address WA1 are , It is updated every time the data block is written, and changes to WA2-1, WA2-2, ....

【0033】

Figure 3 shows the state before the input line interfaces 10-1 and 10-2 output the final data block of the variable length packet. There is no registered data in the output queue corresponding to the output line LO-3, and the output queue Address table entry 310-3 is empty. In the present invention, when the final data block of a packet is written to the common buffer memory 22, the buffer control unit 30 outputs the packet start address BAi and the latest address WAi (= WA) in the input queue of the final data block. It is characterized by moving to the address table 310.

【0034】

When the transfer destination output queue of the data block stored in the input queue is empty, that is, when the queue flag Fj corresponding to the output line number OUT-j output by the header analysis unit 31 is off, the packet start address BAi Move the contents of the latest address WAi to the next read address RAj and the final read address EAj of the output queue address table entry 310-j, respectively, and rewrite the queue flag Fj to the ON state.

【0035】

FIG. 4 shows the operation of the buffer control unit 30 when the final data block D1-5 of the variable length packet output from the input line interface 10-1 is written to the common buffer memory 22. In this case, the buffer control unit 30 stores the write address WA1-5 of the final data block D1-5 in the next address memory 340, and then sets the contents (WA1-1) of the packet start address BA1 of the input queue and the latest address WA1. Move the contents (WA1-5) to RA3 and EA3 of the output queue address table, and rewrite the queue flag F3 to the ON state. Since the content of the latest address WA1 is the new write address WA extracted from the free address FIFO35 this time, the free address FIFO35 is displayed in the output queue address table EA3 instead of the latest address WA1. The write address WA retrieved from may be stored.

【0036】

When the transfer destination output queue of the data block accumulated in the input queue is in use, that is, when the output line number OUT-j output by the header analysis unit 31 and the queue flag Fj corresponding to it are in the on state, the buffer control unit 30 combines the linked address list of the input queue with the linked address list of the forwarding output queue. When the above linked address list is combined, the contents of the packet start address BAi of the input queue are stored in the next address memory 340 as the next address paired with the final data block of the output queue, and the contents of the latest address WAi of the input queue are output. This is achieved by setting it as the final read address EAj in the queue address table 310.

【0037】

Figure 5 shows the buffer when the final data block D2-3 of the variable length packet output from the input line interface 10-2 is written to the common buffer memory 22 when the output queue of the output line LO-3 is already in use. The operation of the control unit 30 is shown. In this case, the buffer control unit 30 stores the write address WA2-3 of the final data block D2-3 in the next address memory 340, and then registers the contents (WA2-1) of the packet start address BA2 of the input queue in the output queue. Write to the next address memory 340 as the next address paired with the finished final data block D1-5. Writing of the start address WA2-1 to the next address memory 340 is performed using the final read address WA1-5 (see FIG. 4) indicated by EA3 in the output queue address table at that time as the write address. After this, EA3 in the output queue address table is rewritten to the contents of the latest address WA2 (WA2-3).

【0038】

If the variable-length packet received by the line interface is short and fits in one fixed-length data block, when writing this data block to the common buffer memory 22, the head display flag signal FP output from the header analysis unit 31 and the final The display flag signal EP is turned on at the same time. In this case, the contents of the packet head address BAi and the latest address WAi registered in the input queue address table 300 in response to the head display flag signal FP are displayed in the output queue address table 310 in response to the final display flag signal EP. Immediately transferred.

【0039】

If the output queue of the output line LO-j, which is the transfer destination of the data block, is empty, the contents of the packet start address BAi and the latest address WAi are written to RAj and EAj as in Fig. 4, and the above output queue If is already in use, the content of the packet start address BAi becomes the next address paired with the final data block of the output queue, and the content of the latest address WAi becomes the new EAj, as in Fig. 5.

【0040】

The data block is read from the common buffer memory 22 by the output queue control unit 33. The output queue control unit 33 refers to the output queue address table entry 310-j specified by the output line selection signal output to the signal line L25 in the read cycle, and if the queue flag Fj is on, the next read. According to the address RAj, the data block is read from the common buffer memory 22 and the next address NAj is read from the next address memory 340. The used next read address RAj is released to the free address FIFO35. The next address NAj read from the next address memory 340 is stored in the output queue address table as a new next read address RAj.

【0041】

FIG. 6 shows one embodiment of the input queue control unit 32. The input queue control unit 32 includes registers 301-1 to 301-n for storing the packet start addresses BA1 to BAn, registers 302-1 to 302-n for storing the latest addresses WA1 to WAn, and header analysis. Decoder 321 that decodes the input line number IN-i received from unit 31 and turns on one of the enable signals WEN-1 to WEN-n, and the output address from registers 302-1 to 302-n. Controls a selector 322 for selecting one of, a selector 323 for selecting one of the output addresses from registers 301-1 to 301-n, and a write enable signal for the packet start address. It consists of AND circuits 324-1 to 324-n for the purpose.

【0042】

The address WA fetched from the free address FIFO35 is input to the registers 302-1 to 302-n that store the latest address, and the latest is received by the enable signals WEN-1 to WEN-n output from the decoder 321 respectively. Address updates are controlled. When the input line number IN-i indicates the i-th input line, the enable signal WEN-i is turned on and the address WA fetched from the free address FIFO35 is set in register 302-i. At this time, the write address {WAi} of the previous data block stored in the register 302-i is selected by the selector 322 and supplied to the next address management unit 34 as the address WAi for writing the next address (pointer address). To.

【0043】

The address WA fetched from the free address FIFO35 is also input to the registers 301-1 to 301-n that store the packet start addresses BA1 to BAn. Writing to these registers is controlled by AND circuits 324-1 to 324-n, and the input line number IN is limited to the write cycle in which the head display flag FP output from the header analysis unit 31 is turned on. The address WA is written to the register 301-i corresponding to -i. The selector 323 selects the output address from the register 301-i corresponding to the input line number IN-i, and outputs it as the packet start address BAi.

【0044】

FIG. 7 shows one embodiment of the output queue control unit 33. The output queue control unit 33 includes registers 311-1 to 311-n for storing the next read addresses RA1 to RAn, registers 312-1 to 312-n for storing the final read addresses EA1 to EAn, and a queue. Registers 313-1 to 313-n for storing flags F1 to Fn, selector 331 for selecting one of the output addresses from registers 311-1 to 311-n, and registers 312-1 to A selector 332 for selecting one of the output addresses from 312-n, a selector 333 for selecting one of the output flags from registers 313-1 to 313-n, and an output counter 25. Decoder 334 for decoding the output line selection signal output to the signal line 25 from, and the output line number OUT-j output from the header analysis unit 31 are decoded, and the enable signals EN-1 to EN-n To enable the above enable signals EN-1 to EN-n when the decoder 335 that turns on one of them and the final display flag signal EP output from the header analysis unit 31 are turned on. AND circuits 336-1 to 336-n, delay circuits 337-1 to 337-n inserted between AND circuits 336-1 to 336-n and registers 313-1 to 313-n, and registers 313- It consists of AND circuits 338-1 to 338-n inserted between 1 to 313-n and registers 311-1 to 311-n.

【0045】

The write address WA fetched from the free address FIFO35 is input to the registers 312-1 to 312-n for storing the final read addresses EA1 to EAn, and the outputs of the AND circuits 336-1 to 336-n are written respectively. It is an enable signal. When the final display flag signal EP is turned on, the write enable signal from the AND circuit 336-j corresponding to the output line number OUT-j becomes valid, and the write address WA is set in the register 312-j. Since the write address WA in this case is the write address WAi of the final data block of the variable-length packet in the input queue address table 300, the address WAi of the input queue becomes the final read address ENj of the output queue. It will have been moved to.

【0046】

The outputs of the registers 312-1 to 312-n are connected to the selector 332 whose selection signal is the output line number OUT-j output from the header analysis unit 31, and are specified by the output line number OUT-j. The output address EAj from register 312-j is selected and supplied to the next address management unit 34.

【0047】

The outputs of the AND circuits 336-1 to 336-n are given as set signals to the registers 313-1 to 313-n for storing the cue flags F1 to Fn, respectively. The outputs of these registers 313-1 to 313-n are connected to the selector 333 whose selection signal is the output line number OUT-j, and the queue flag of the register 313-j specified by the output line number OUT-j. Fj is selected and supplied to the next address management unit 34.

【0048】

Here, the outputs of the AND circuits 336-1 to 336-n are supplied to the registers 313-1 to 313-n via the delay circuits 337-1 to 337-n. Therefore, the queue flag Fj from the register 313-j selected by the selector 333 indicates the state of the queue flag before being rewritten by the final display flag signal EP, and after the above queue flag Fj is output, the register 313- A new queue flag is set in j.

【0049】

The registers 311-1 to 311-n for storing the next read addresses RA1 to RAn include the packet start address BAi output from the input queue control unit 32 and the next address NAi output from the next address management unit 34. Has been entered. The AND circuits 318-, which input the output of the AND circuits 336-1 to 336-n and the negative output of the registers 313-1 to 313-n, respectively, to these registers 311-1 to 311-n in the write cycle. When the output signals from 1 to 318-n are given as enable signals and the final display flag signal EP is turned on, the corresponding queue flag of register 313-j specified by the output line number OUT-j The packet start address BAi is stored in the register 311-j specified by the output line number OUT-j, provided that Fj is in the off state.

【0050】

In the read cycle, an enable signal is given from the decoder 334 to the register 311-j specified by the output line selection signal, the address RAj stored in the register 311-j is selected by the selector 331, and the common buffer memory 22 Is supplied to the next address management unit 34. Further, the next address NAj read from the next address memory 340 by the next address management unit 34 is written to the register 311-j as a new next read address RAj.

【0051】

Although the display of the reset circuit is omitted in FIG. 7 for the sake of simplicity, the comparison result between the final address EAj and the packet start address RAj is used for the reset signal of the register 313-j. That is, when the final read address EAj and the next read address RAj match, the output queue becomes empty in the next read cycle, so the queue flag Fj is reset. To reset the register 313-j, for example, a comparison circuit for detecting a match between the output of the selector 332 and the output of the selector 331 is provided, and the match detection signal output from this comparison circuit is used.

【0052】

FIG. 8 shows one embodiment of the next address management unit 34. The next address management unit 34 has registers 340-1 to 340-m for storing the next addresses NA1 to NAm, a selector 341 for selecting the output address from these registers, and a write address fetched from the free address FIFO35. Selector 342 for selecting one of the packet start address BAi supplied from WA and the input queue control unit 32, and the latest address WAi supplied from the input queue control unit 32 and the final read supplied from the output queue control unit 33. It consists of a selector 343 for selecting one of the address EAj, a decoder 344 connected to the selector 343, and an AND circuit 345.

【0053】

The final display flag signal EP supplied from the header analysis unit 31, the queue flag Fj supplied from the output queue control unit 33, and the clock signal CLK0 are input to the AND circuit 345. The CLK0 is a signal that changes to the Low state in the first half of the write cycle of each data block and to the High state in the second half.

【0054】

In the write cycle, the selector 342 selects the write address WA when the output signal of the AND circuit 345 is off, and the packet head address BAi when the output signal is on, and registers these in registers 340-1 to 340-. Let it be the input data of m. The selector 343 selects the write address WAi of the previous data block when the output signal of the AND circuit 345 is off, and selects the final read address EAj of the preceding packet when the output signal is on, and the decoder. Enter in 344. The decoder 344 decodes the address input from the selector 343 and gives a write enable signal to the register 340-k corresponding to the input address.

【0055】

Of the three signals EP, Fj, and CLK0 input to the AND circuit 345, CLK0 is always in the Low state in the first half of each write cycle, so in the first half of each write cycle, it is irrelevant to the states of the input signals EP and Fj. The output of the AND circuit 345 is turned off, and the selectors 342 and 343 select WA and WAi, respectively. Therefore, the write address WA of the latest data block is stored in the storage area (register 340-k) corresponding to the write address WAi of the previous data block, thereby forming a linked address list for each input queue shown in FIG. Will be done.

【0056】

In the latter half of each write cycle, CLK0 is in the High state, so the output of the AND circuit 345 differs depending on the state of the input signals EP and Fj. When both the input signals EP and Fj are in the High state, the AND circuit 345 The output changes to the on state. That is, when the data block written to the common buffer is the final data block of the variable length packet (signal EP is High) registered in the output queue in use (signal Fj is High), the output of the AND circuit 345 is output. In the ON state, selectors 342 and 343 select BAi and EAj, respectively, and the start address BAi of the variable-length packet is stored in the storage area (register 340-q) specified by the final write address EAj of the output queue. This makes it possible to link the data block sequence (linked address list) of the succeeding packet to the final data block of the preceding packet in the output queue.

【0057】

When the data block written to the common buffer is the first data block or intermediate data block of the variable length packet (signal EP is Low), or the variable length packet registered in the free output queue (signal Fj is Low). In the case of the final data block of, since the write cycle ends with the output of the AND circuit 345 in the Low state, the operation of adding the linked address list to the output queue described above does not occur.

【0058】

In the read cycle, the selector 341 selects the register 340-p corresponding to the read address RAj supplied from the output queue control unit 33, and the address stored in the above register in 340-p is used as the next address NAj for output queue control. Return to part 33. The next address NAj is stored in the register 311-j as a new next read address RAj to be used in the next read cycle in the output queue control unit 33.

【0059】

In the above embodiment, the buffer control unit 30 forms an input queue for each input line number, and moves the linked address list of the input queue to the output queue when the last data block of the variable length packet arrives. However, in the present invention, since each input queue may be formed for each variable length packet, other identification information unique to each variable length packet may be used instead of the input line number. In the embodiment, the input line number is set in the internal header of each data block, and the header analysis unit 31 outputs the input line number IN-j based on the above internal header. However, the input line number IN-j is an input counter. It may be generated based on the input line selection signal output from 24.

【0060】

Further, in the above-described embodiment, each input line interface 10-i (i = 1 to n) divides the variable length packet 100 received from the input line into a plurality of fixed-length data blocks 110, and divides the variable length packet 100 into a plurality of fixed-length data blocks 110. The data block with the internal header is output to the multiplexing unit 21 with the internal header 110A attached, and the data block with the internal header is read and written to the common buffer memory 22. However, as another embodiment of the present invention, for example, As shown in FIG. 9, the data block 110 and the internal header 110A are separated by the multiplexing unit 21, the internal header 110A is supplied to the header analysis unit 31 of the buffer control unit 30, and the data block 110 portion is stored in the common buffer memory 22. You may enter only. According to the above configuration, the memory capacity of the common buffer memory 22 can be effectively used, and it is not necessary to remove the internal header from the data block at each output line interface 20-i.

【0061】

As still another embodiment of the present invention, each input line interface 10-i outputs the fixed-length data block 110 to the multiplexing unit 21 without attaching an internal header, and the header analysis unit 31 of the buffer control unit 30 The packet header included in the head data block of each variable length packet is analyzed, the output line number and the number of subsequent data blocks are managed on the management table for each input line, and the input line selection signal given from the input counter 24 is managed. Depending on the situation, the above-mentioned management table may be referred to to generate the above-mentioned control signals such as IN-i, FP, EP, and OUT-j. Further, the conversion from the variable length packet 100 to the fixed length data block 110 may be performed by the multiplexing unit 21 instead of being performed by each input line interface 10-i.

【0062】

In the embodiment, a packet switch connected to a plurality of input / output lines has been described, but the buffer control of the present invention has a switch structure (multiplexing) that outputs variable length packets received from a plurality of input lines to one output line. It can also be applied to devices).

【0063】

[Effect of the invention]

As is clear from the above description, in the present invention, an input queue is formed for each variable length packet, and when the last data block of one variable length packet is written to the buffer memory, the input queue is set as described above. It is moved to the output queue corresponding to the output line of the variable length packet. Therefore, according to the present invention, even when a plurality of variable-length packets destined for the same output line are input in parallel, the data of other packets is included in the data block string belonging to one variable-length packet in the output queue. It is possible to prevent the blocks from being mixed, and by sequentially sending the data blocks taken out from the output queue to the output line, it is possible to correctly transfer the received packet to the destination device.

【0064】

Further, in the present invention, the variable-length packet received from the input line is divided into fixed-length data blocks and stored in the common buffer memory in fixed-length block units, and the final data block of the variable-length packet is stored. At that point, the configuration is such that only the linked address list for reading the above data block string is moved to the output queue without moving the accumulated data block string in the common buffer memory. High-speed switching is possible.

[Simple explanation of drawings]

[Figure 1]

The figure which shows one Example of the packet switch to which this invention was applied.

[Figure 2]

The figure which shows the detail of the buffer control part 30 of the packet switch shown in FIG. A conceptual diagram showing the first state of the input queue and the output queue.

[Fig. 3]

The figure for demonstrating the state of the data block stored in the common buffer memory 22, the next address memory 340, and the input queue address table 300.

[Fig. 4]

The figure for demonstrating the relationship between the input queue address table 300 and the output queue address table 310 when the last data block of a variable length packet arrives.

[Fig. 5]

The figure for demonstrating the relationship between the input queue address table 300 and the output queue address table 310 when the last data block of another variable-length packet arrives when the output queue is in use.

[Fig. 6]

The figure which shows 1 Example of the input queue control part 32 shown in FIG.

[Fig. 7]

The figure which shows 1 Example of the output queue control part 33 shown in FIG.

[Fig. 8]

The figure which shows 1 Example of the next address management part 34 shown in FIG.

[Fig. 9]

The figure which shows the other embodiment of the packet switch to which this invention is applied.

[Explanation of symbols]

1: Packet switch, 10: Input line interface, 20: Output line interface, 21: Multiplexing unit, 22: Common buffer memory, 23: Separation unit, 24: Input counter, 25: Output counter, 30: Buffer control unit, LI: Input line, LO: Output line, 31: Header analysis unit, 32: Input queue control unit, 33: Output queue control unit, 34: Next address management unit, 35: Free address FIFO, 300: Input queue address table , 301 (BA1 ~ BAn): Packet start address, 302 (WA1 ~ WAn): Latest address, 310: Output queue address table, 311 (RA1 ~ RAn): Next read address, 312 (EA1 ~ EAn): Last read Address, 313 (F1 ~ Fn): Queue flag.