HIERARCHICAL SWITCHING FABRIC AND DEADLOCK AVOIDANCE METHOD FOR ULTRA HIGH RADIX NETWORK ROUTERS

Abstract

This invention discloses a hierarchical switching fabric and deadlock avoidance method for ultra high radix network routers. The hierarchical switching fabric comprises a network-on-chip and K multi-port components. The multi-port component comprises a port module configured to receive packets by a high speed serializer/deserializer, code and format the packets, send the packets to a corresponding hyper packet module after coding and format conversion, and send the packets sent by the hyper packet module to the network; and the hyper packet module configured to perform protocol processing for the received data link level packets, discard illegal packets, forward legitimate packets to the network-on-chip, perform data error correcting, format conversion and channel mapping for the packets received from the network-on-chip, and send the packets to the corresponding port module.

Claims

1. A hierarchical switching fabric for ultra high radix network routers, comprising: a network-on-chip and K multi-port components configured to converge multiple switching ports; the multi-port component comprises a port module and a hyper packet module; the port module configured to receive packets from the network-on-chip over a high speed serializer/deserializer, encode and format the packets, send the packets to the corresponding hyper packet module after coding and format conversion, and send the packets sent by the corresponding hyper packet module to the network-on-chip; and the hyper packet module configured to perform protocol processing for the received data link level packets, discard illegal packets, forward legitimate packets to the network-on-chip for switching, perform data error correcting, format conversion and channel mapping for the packets received from the network-on-chip, and send the packets to the corresponding port module.

2. The hierarchical switching fabric for ultra high radix network routers as recited in claim 1, wherein the port module comprises physical coding sublayer submodules and M data link level protocol submodules; the physical coding sublayer submodules are connected with the network-on-chip via the high speed serializer/deserializer, and are respectively connected with the hyper packet modules via the M data link level protocol submodules, and the physical coding sublayer submodules are configured to align and reorganize packet data, and the data link level protocol submodules are configured to perform packet format conversion and protocol processing.

3. The hierarchical switching fabric for ultra high radix network routers as recited in claim 2, wherein the hyper packet module comprises an ingress hyper packet logic and an egress hyper packet logic; the ingress hyper packet logic comprises M identical port protocol processing logics, a first multiplexer element, a dynamic allocated multi-queue element and a second multiplexer element; the port protocol processing logic comprises an hyper packet element, a routing computing element, an error correcting code generator, and a first in first out queue buffer; the hyper packet element and the routing computing element are connected in parallel, and then connected with an input end of the first in first out queue buffer via the error correcting code generator; the packets from the port module are entered into the corresponding port protocol processing logic; the first multiplexer element selects the packets in each of the port protocol processing logics in turn and stores the packets in the dynamic allocated multi-queue element, and the second multiplexer element is configured to output the packets stored in the dynamic allocated multi-queue element to the network-on-chip.

4. The hierarchical switching fabric for ultra high radix network routers as recited in claim 3, wherein the egress hyper packet logic comprises a data error correcting element, a virtual channel to virtual channel element, and M identical packet format gearboxes; the packets from the network-on-chip pass through the data error correcting element and the virtual channel to virtual channel element, and then output to the port module through the packet format gearboxes.

5. The hierarchical switching fabric for ultra high radix network routers as recited in claim 3, wherein the hyper packet element comprises a packet checking logic, a partition key checking logic and a sequence packet checking logic successively connected.

6. The hierarchical switching fabric for ultra high radix network routers as recited in claim 3, wherein the routing computing element comprises a routing address computing logic, a routing address lookup logic, a routing address lookup logic, routing address error correcting logic and a routing mode selection logic successively connected.

7. The hierarchical switching fabric for ultra high radix network routers as recited in claim 3, wherein the dynamic allocated multi-queue element consists of 16-virtual channel shared buffer memories, and every two port protocol processing logics are set to share one 16-virtual channel shared buffer memory.

8. The hierarchical switching fabric for ultra high radix network routers as recited in claim 3, wherein each dynamic allocated multi-queue element comprises a tail slice dynamic allocated multi-queue configured to record whether a tail slice arrives and anomaly detection information upon arrival; a control dynamic allocated multi-queue, that is routing computing information, configured to record head slice information and anomaly detection information upon arrival of the head slice; and a data dynamic allocated multi-queue configured to record data payload and error correcting code data protection information.

9. A deadlock avoidance method for the hierarchical switching fabric for ultra high radix network routers, comprising: a port module PORT, of a uth multi-port component receives packets from a network-on-chip via a high speed serializer/deserializer; the port module PORT, encodes and converts format of the packets and sends the packets to a hyper packet module HP.sub.u of the uth multi-port component; and the hyper packet module HP.sub.u performs protocol processing for received data link level packets, discards illegal packets, and forwards legitimate packets to a network-on-chip for switching; the network-on-chip performs column switching for the packets received from the hyper packet module HP.sub.u according to packet control information, and sends the packets to acorresponding hyper packet module HP.sub.v of the vth multi-port component; and the hyper packet module HP.sub.v performs data error correcting, format conversion and channel mapping for the packets received from the network-on-chip, and sends the packets to the port module PORT.sub.v of the vth multi-port component; and the port module PORT.sub.v performs format conversion and protocol processing for the packets, and then sends the packets to a network router chip or network interface chip of the next level via the high speed serializer/deserializer.

10. The deadlock avoidance method as recited in claim 9 for the hierarchical switching fabric for ultra high radix network routers, wherein the port module PORT.sub.u encodes and converts format of the packets and sends the packets to a hyper packet module HP.sub.u of the uth multi-port component; and the hyper packet module HP.sub.u performs protocol processing for received data link level packets, discards illegal packets, and forwards legitimate packets to a network-on-chip for switching, comprising: physical coding sublayer submodules of the port module PORT.sub.u reorganizes and align the received packets and forwards the packets to corresponding data link level protocol submodules LLP.sub.x for processing; the data link level protocol submodules LLP.sub.x performs coding and error correcting for the packets, and sends the packets to a corresponding port protocol processing logic HPORT.sub.x in the hyper packet module HP.sub.u of the uth multi-port component; and the port protocol processing logic HPORT.sub.x sends the packets to a x*M*P+x*P+sth virtual channel shared buffer over a receiving end virtual channel of the network-on-chip according to number of virtual channels s, wherein x and s are integers, 0≤x<M−1, 0≤s≤P−1, and P is a number of the virtual channels for each buffer, that is, each packet can be sent or received from one of the P channels.

11. The deadlock avoidance method as recited in claim 9 for the hierarchical switching fabric for ultra high radix network routers, wherein the network-on-chip performs column switching for the packets received from the hyper packet module HP.sub.u according to packet control information, and sends the packets to acorresponding hyper packet module HP.sub.v of the with multi-port component, comprising: the network-on-chip extracts the packets from the receiving end virtual channel buffer for the column switching, stores the packets in a transmitting end virtual channel buffer of the network-on-chip, extracts the packets from a tth transmitting end virtual channel buffer VC.sub.t and sends the packets to a packet format gearboxes GB.sub.y in the hyper packet module HP.sub.v of the vth multi-port component, wherein t and y are integers, 0≤t≤M*M*P−1, 0≤y≤M−1, y=t %(M*P), and y is a remainder oft divided by M*P.

12. The deadlock avoidance method as recited in claim 9 for the hierarchical switching fabric for ultra high radix network routers, wherein the hyper packet module HP.sub.v performs data error correcting, format conversion and channel mapping for the packets received from the network-on-chip, and sends the packets to the port module PORT.sub.v of the vth multi-port component; and the port module PORT.sub.v performs format conversion and protocol processing for the packets, and then sends the packets to a network router chip or network interface chip of the next level via the high speed serializer/deserializer, comprising: the hyper packet module HP.sub.v performs error correcting and channel mapping for the packets received from the network-on-chip, converts the packets into data link level protocol packets through the yth packet format gearboxes GB.sub.y, and sends the packets to the data link level protocol submodule LLP.sub.y in the port module PORT.sub.v of the vth multi-port component; the data link level protocol submodule LLP.sub.y parses the packets, and sends the packets to the physical coding sublayer submodule in the port module PORT.sub.v; and the physical coding sublayer submodule reorganizes and aligns the packets, and then sends the packets to the network router chip or network interface chip of the next level via the high speed serializer/deserializer.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0021] FIG. 1 is a structural diagram of a hierarchical switching fabric in the application of this invention.

[0022] FIG. 2 is a structural diagram of a multi-port component in the application of this invention.

[0023] FIG. 3 illustrates the entry protocol processing structure of a hyper packet module (HP module) in the application of this invention.

[0024] FIG. 4 is a flowchart of a deadlock avoidance method for a network router chip in the application of this invention.

DESCRIPTION OF THE EMBODIMENTS

[0025] As shown in FIG. 1, a hierarchical switching fabric for ultra high radix network routers in this embodiment comprises a network-on-chip (NOC) and K multi-port components configured to converge multiple switching ports (a 0th MPORT module, . . . , a kth MPORT module, . . . , and a K-1th MPORT module). Number of the switching ports of the ultra high radix network router is recorded as N, every M switching ports are converged into a multi-port component, packets of K multi-port components are subject to full switching by a network-on-chip (NOC), the K multi-port components have identical structures, M, N, K and k are integers, M is a factor of N, that is, N can be divided by M exactly, K=N/M, 0≤k≤K−1. Packet switching in a network router chip (NR) chip can be divided into two levels: packet switching in the multi-port components and packet switching in the NOC.

[0026] As shown in FIG. 2, the multi-port component comprises:

[0027] a port module (PORT module) configured to receive packets from the NOC via a high speed serializer/deserializer (SerDes), encode and format the packets, send the packets to a corresponding hyper packet module (HP module) after coding and format conversion, and send the packets sent by the corresponding HP module to the NOC; and

[0028] the hyper packet module (HP module) configured to perform protocol processing for the received data link level packets, discard illegal packets, forward legitimate packets to the NOC for switching, perform data error correcting, format conversion and channel mapping for the packets received from the NOC, and send the packets to the corresponding port module.

[0029] The port module and the HP module in the kth multi-port component are recorded as PORT.sub.k and HP.sub.k respectively. If the uth multi-port component is an input port and the vth multi-port component is an output port, the port module PORT.sub.u in the uth multi-port component receives packets from the NOC via the high speed SerDes, encodes and formats the packets, and sends the packets to a corresponding HP module HP.sub.u after coding and format conversion. The HP module HP.sub.u performs protocol processing for received data link level packets, discards illegal packets, and forwards legitimate packets to the NOC for switching. The NOC performs column switching for the packets received from the HP module HP.sub.u, sends the packets to an HP module HP.sub.v of the corresponding vth multi-port component. The HP module HP.sub.v performs data error correcting, format conversion and channel mapping for the packets received from the NOC, and sends the packets to the port module PORT.sub.v. The port module PORT.sub.v performs format conversion and protocol processing for the packets, and then sends the packets to a NR chip of the next level by the high speed SerDes, wherein u and v are integers, 0≤u≤K−1, and 0≤v≤K−1.

[0030] As shown in FIG. 2, the port module comprises physical coding sublayer (PCS) submodules and M data link level protocol (LLP) submodules (LLP.sub.0 to LLP.sub.M−1), the PCS submodules are connected with the NOC via the high speed SerDes, and are respectively connected with the HP modules over the M data LLP submodules (LLP.sub.0 to LLP.sub.M−1), the PCS submodules are configured to align and reorganize packet data, and the data LLP submodules (LLP.sub.0 to LLP.sub.M−1) are configured to perform packet format conversion and protocol processing.

[0031] As shown in FIG. 2, the HP module comprises an ingress hyper packet logic (HP_Ingress) and an egress hyper packet logic (HP_Egress). The HP_Ingress is configured to receive data LLP packets from the data LLP submodule of the port module, process high speed packet protocols, perform validity check, partition check, hop number check, channel switching, routing computing and format conversion on the packets, discard illegal packets, make relevant records, and forward the legitimate packets to the NOC for switching, and finally transmit the legitimate packets to the data LLP ports via the NOC and send to the network router chip (NR chip) of the next level. The HP_Egress is configured to receive packets from the NOC, perform error correcting, channel mapping and format conversion for the packets received from the NOC, converts the packets received from the NOC into data LLP packets, and send the packets to the data LLP submodule in the port module.

[0032] As shown in FIG. 2 and FIG. 3, the HP_Ingress comprises M identical port protocol processing logics (HPORT.sub.0 to HPORT.sub.M−1), a first multiplexer element (Mux4), a dynamic allocated multi-queue (DAMQ) element and a second multiplexer element (Mux32). HPORT.sub.i represents an ith port protocol processing logic, i is an integer, and 0≤i≤M−1.

[0033] As shown in FIG. 2 and FIG. 3, the port protocol processing logic comprises a hyper packet (HP) element, a routing computing (RC) element, an error correcting code generator (ECC_GEN) and a first in first out (FIFO) queue buffer. The HP element and the RC element are connected in parallel, and then connected with an input end of the FIFO queue buffer via the ECC_GEN. The packets from the port module are entered into the corresponding port protocol processing logic. The first multiplexer element selects the packets in each of the port protocol processing logics in turn and stores the packets in the DAMQ element, and the second multiplexer element is configured to output the packets stored in the DAMQ element to the NOC.

[0034] As shown in FIG. 2 and FIG. 3, the HP_Egress comprises a data error correcting (DEC) element, a virtual channel to virtual channel (VC2VC) element and M identical packet format gearboxes (GB) element, and the packets from the NOC pass through the DEC element and the VC2VC element in turn, and are output to the port module through the packet format GB element.

[0035] As shown in FIG. 3, the HP element comprises a packet checking (PC) logic, a partition key checking (PKC) logic and a sequence packet checking (SPC) logic connected in turn. It should be noted that both the PC logic and the PKC logic are to validate format of the packets, while the SPC logic is to check sequence continuity of the packets. Such validation and checking are available in the related art, so they are not repeated here.

[0036] As shown in FIG. 3, the RC element comprises a routing address computing logic rtb_addr_gen, a routing address lookup logic rtb_mem, a routing address error correcting logic rtb_ecc_chk and a routing mode selection logic rtb_port_select connected in turn. It should be noted that the routing address computing, the routing address lookup, the routing address error correcting, and the routing mode selection are all routine methods for path processing, so they are not discussed in detail here.

[0037] As noted above, the parallel processing mode of HP and RC is used in each port protocol processing logic in this application. Each port protocol processing logic receives the packets from the port module. The HP element and the RC element conduct the HP and the RC in parallel, and then send the legitimate packets and RC results to the ECC correcting logic. The ECC correcting logic protects key packet information, stores packet data information, control information and error correcting information into the FIFO queue buffer of the port protocol processing logic, and then the first multiplexer element circularly reads the data in the FIFO queue buffer of each port protocol processing logic, and stores the data into the buffer of the DAMQ element.

[0038] In this application, the DAMQ element is composed of 16-virtual channel shared buffer memories, and every two port protocol processing logics are set to share one 16-virtual channel shared buffer memory. A core clock frequency of the NR chip is recorded as C MHZ, length of the LLP packet is recorded as W.sub.1 bits, and width of single DAMQ input data is recorded as W.sub.2 bits, the maximum input bandwidth of the LLP is W.sub.1*C bps, and the maximum input bandwidth of the DAMQ is W.sub.2*C bps. C, W.sub.1 and W.sub.2 are positive integers, and 2*W.sub.1≤W.sub.2. In order to avoid network congestion, every two port protocol processing logics are set to share one 16-virtual channel shared buffer memory in this application. The first multiplexer element performs seamless circular priority scheduling of packet slices from different port protocol processing logic combinations to ensure that there is no exception to the FIFO queue buffer inside each port protocol processing logic.

[0039] As shown in FIG. 3, each DAMQ element comprises a tail slice DAMQ (TAIL DAMQ) configured to record whether a tail slice arrives and anomaly detection information upon arrival, a control DAMQ (CRTL DAMQ) configured to record head slice information and anomaly detection information (i.e. RC information) upon arrival of the head slice, and a data DAMQ (DATA DAMQ) configured to record data payload and ECC data protection information. Data of the data path is subject to ECC protection in the NR chip, and there are three buffers in the data path, namely input buffer, line buffer and column buffer. All buffers have ECC codes, and are divided into data buffer and control buffer. Values of the line buffer comprises head and tail, virtual channel, line number of destination Tile, destination port number, order-preserving and dimension conversion for arbitration. The data buffer transmits data according to arbitration results. In order to ensure data correctness for the control buffer, every read-write will be subject to ECC correcting operation. For the data buffer, the input buffer is used for ECC coding, and data is read from the column buffer for ECC decoding. ECC coding protection is available for CRTL DAMQ and TAIL DAMQ. However, the DATA DAMQ is subject to ECC computing at an HP input port and sub-ECC correcting at an HP output port. Due to large width of the DATA DAMQ, the DAMQ is divided into TAIL DAMQ, CRTL DAMQ and DATA DAMQ. The DATA DAMQ performs ECC computing at an input port of the HP module and ECC correcting at an output port of the HP module, which is advantageous to protect the data on the whole chip, effectively saving hardware resources and avoiding unnecessary timing critical path.

[0040] The first multiplexer element (Mux4) is configured to read a packet from the buffer of the DAMQ element, generate an NOC packet according to the destination port number and virtual channel number of the packet, and send the NOC packet to the NOC for switching. The packet sent to the NOC is subject to line and column switching in the NOC according to control information field selection in the packet, and sends the packet to the corresponding NOC output port to send to other multi-port components in the NR chip.

[0041] In the NR chip, the packet can be transmitted based on credit control which has advantages of high transmission rate, low transmission delay and no loss of data packets. However, network congestion will occur when load of a switching node or destination node exceeds the maximum processing capacity of the network, resulting in chip deadlock, thus reducing overall performance of the network. In order to realize deadlock-free packet switching of N ports, this application further provides a deadlock avoidance method using the hierarchical switching fabric for the hyper packet (HP) in a network router (NR) chip and deadlock-free switching in a network-on-chip (NOC), and avoidance of deadlock problem resulting from data congestion in the NR chip. As mentioned above, there are M switching ports in each HP module and M data link level protocol (LLP) submodules in each port module. Network packets are transmitted over P VCs, M*M*P receiving end VC buffers and transmitting end VC buffers are set in the NOC, and P is a positive integer. As shown in FIG. 4, the deadlock avoidance method used for a hierarchical switching fabric for ultra high radix network routers are implemented as follows:

[0042] 1) a port module PORT.sub.u of a uth multi-port component receives packets from a network via a high speed serializer/deserializer (SerDes);

[0043] 2) the port module PORT, encodes and converts format of the packets and sends the packets to a hyper packet (HP) module HP.sub.u of the uth multi-port component; The HP module HP.sub.u performs protocol processing for received data link level packets, discards illegal packets, and forwards legitimate packets to the NOC for switching;

[0044] 3) the NOC performs column switching for the packets received from the HP module HP.sub.u according to packet control information, and sends the packets to an HP module HP.sub.v of the corresponding vth multi-port component; and

[0045] 4) the HP module HP.sub.v performs data error correcting, format conversion and channel mapping for the packets received from the NOC, and sends the packets to the port module PORT.sub.v of the vth multi-port component; and the port module PORT.sub.v performs format conversion and protocol processing for the packets, and then sends the packets to a network router (NR) chip or network interface chip of the next level via the high speed SerDes.

[0046] In this application, step 2) is detailed as follows: a PCS submodule of the port module PORT.sub.u reorganizes and align the received packets and forwards the packets to a corresponding data LLP submodule LLPx for processing; the data LLP submodule LLP.sub.x performs coding and error correcting for the packets, and sends the packets to a corresponding port protocol processing logic HPORT.sub.x in the HP module HP.sub.u of the uth multi-port component; and the port protocol processing logic HPORT.sub.x sends the packets to a x*M*P+x*P+sth virtual channel shared buffer over a receiving end virtual channel of the NOC according to number of virtual channels s, wherein x and s are integers, 0≤x<M−1, 0≤s≤P−1, P is a number of the virtual channels for each buffer, that is, each packet can be sent or received from one of the P channels.

[0047] In this application, step 3) is detailed as follows: the NOC extracts the packets from the receiving end virtual channel buffer for the column switching, stores the packets in a transmitting end virtual channel buffer of the NOC, extracts the packets from a tth transmitting end virtual channel buffer VC.sub.t and sends the packets to a packet format GB GB.sub.y in the HP module HP.sub.v of the vth multi-port component, wherein t and y are integers, 0≤t<M*M*P−1, 0≤y≤M−1, y=t %(M*P), and y is a remainder oft divided by M*P.

[0048] In this application, step 4) is detailed as follows: the HP module HP.sub.v performs error correcting and channel mapping for the packets received from the NOC, converts the packets into data LLP packets through GB.sub.y of the yth packet format GB, and sends the packets to the data LLP submodule LLP.sub.y in the port module PORT, of the vth multi-port component. The data LLP submodule LLP.sub.y parses the packets, and sends the packets to the PCS submodule in the port module PORT.sub.v; and the PCS submodule reorganizes and aligns the packets, and then sends the packets to the NR chip or network interface chip of the next level by the high speed SerDes.

[0049] The technical problem to be solved by this invention is to provide a hierarchical switching fabric for ultra high radix network routers and a deadlock avoidance method in view of characteristics of the ultra high radix network router in the related art such as occupation of too much network resources due to excessive switching ports, much switching delay and insufficient buffer resources (which may lead to chip deadlock). The invention can improve network switching efficiency, reduce packet switching delay, and effectively avoid deadlock problem in packet switching in the ultra high radix network routers, and can be widely used in super advanced chip design.

[0050] Compared with the related art, this invention has the following advantages:

[0051] 1. A two-level switching fabric composed of multi-port components and the NOC are arranged in the ultra high radix network router; The switching in the multi-port components uses parallel processing of hyper packet and routing computing. The hyper packet can be completed in one clock cycle, and the routing computing can be completed in three clock cycles. The design of this invention can realize the parallel execution of the hyper packet and the routing computing, effectively reduce length of timing path of packet protocol parsing, and save hardware resources.

[0052] 2. This invention can realize deadlock-free switching in the multi-port components and the NOC in the network switching, avoid deadlock caused by data congestion in NR chips, and realize high-bandwidth and low-delay data transmission of network packets in NR chips.

[0053] The above are only preferred applications of this invention, and the protection scope of this invention is not limited to the applications mentioned above. All the technical solutions with the ideas of this invention fall into the protection scope of this invention. It should be pointed out that, for an ordinary person skilled in the art, some improvements and modifications without deviating from the principle of this invention shall be deemed as the protection scope of this invention.