System and method for reducing capacity demand of ethernet switch controller

[0002] The present invention relates to a device and method to be applied to a switch fabric controller, particularly applied to an Ethernet switch fabric controller for reducing circuit capacity demand or circuit size.

[0003] As shown in FIG. 1, a conventional Ethernet switch fabric controller 10 for controlling the switching operation of an Ethernet switch 20, comprises a plurality of command interpreters 13 each associated with an input port of the Ethernet switch, a read/write server 14, and an output port buffer composed of a plurality of output port buffer units 16. When an input port requests packet forwarding (or switching) to an output port, its packet header will be temporarily saved in the command interpreter 13 waiting for the polling by the Read/Writer Server. The Read/Writer Server periodically checks each command interpreter 13 to decode the packet header therein and forward the packet header to a corresponding output port buffer unit according to the decoding. The Ethernet switch 20 forwards the packet in the input port which has had packet header forwarded to the corresponding output port buffer unit, to the output port which is associated with the corresponding output port buffer unit.

[0004] The Read/Writer Server 14 comprises a sequential polling controller for polling each command interpreter 13 to forward the packet header in an input port to a corresponding output port buffer unit indicated by the packet header. The polling operation of an Ethernet switch fabric controller is subject to two requirements: fair and fast. Fair operation means each input port must be polled periodically with the same period or the same frequency while fast operation means Full Line Traffic characterized in that the processing time for a packet header in a Ethernet switch fabric controller shall be no more than 960 ns, in order to eliminate the possibility of Latency Delay longer than 960 ns for a packet forwarding in an Ethernet Switch Fabric controller.

[0005] The output port buffer unit is for saving packet header when there are two or more than two packet headers to be forwarded to the same output port, or when a packet header is to be forwarded to an output port which has not yet completed the processing of a packet header already saved therein.

[0006] The Ethernet switch forwards the packet in an input port (which had requested a packet switching) to an output port which corresponds to the packet header of the packet in the input port. A packet header is saved in a corresponding output port buffer unit before forwarding (or switching) of its packet is completed or processed. An overflow occurs when the number of input ports requesting packet switching to the same output port is larger than the length of the output port buffer unit. The length of an output port buffer unit means the number of memory units each for saving a packet header corresponding to the output port buffer unit. The simplest way to design the output port buffer unit is to have it composed of N memory units to avoid the overflow, with N equal to the number of input ports. For example, N equals 32 (means that the length of each of 32 output port buffer units is 32) if the number of input ports of the Ethernet switch is 32. The kind of design, however, inevitably results in a large number of logic gates in an Ethernet switch fabric controller, and leads to significantly low capacity utilization rate. For example, such a conventional design requires 32*32=1024 memory units for a system with 32 input ports. A better design is therefore strongly expected.

[0007] The length of the output port buffer unit shall be designed so as to minimize the number of logic gates required for an Ethernet switch fabric controller. The Read/Writer Server must be so designed that it can determine and/or control the forwarding operation of each packet header from a input port to an output port.

[0008] Definitions

[0009] A*B: mathematical product of A and B where A and B are any numbers.

[0010] Corresponding output port buffer unit of a packet header: the output port buffer unit with identification code corresponding to a code indicated by the packet header usually for selecting the output port to which the packet containing the packet header shall be forwarded (or switched).

[0011] Destination output port buffer unit of a packet header: the output port buffer unit with identification code corresponding to a destination address code indicated by the packet header usually for pointing to the output port to which the packet containing the packet header shall be forwarded (or switched).

[0012] Length of a buffer unit (temporary buffer unit or output port buffer unit): number of the buffer unit's memory units each for saving a packet header.

[0013] Memory unit: each memory unit for saving a packet header.

[0014] Recognize a packet header: read the code or destination address code indicated by a packet header in order to know the destination output port of the packet header.

[0015] Retrieve a packet header from an input port: move a packet header from an input port and decode the packet header to know the destination output port of the packet header.

[0016] Objects

[0017] An object of the present invention is to provide an Ethernet switch fabric controller requiring output port buffer unit of less capacity (output port buffer unit of length smaller than the number of input ports, for example) while still working with an Ethernet switch to smoothly forward the packet from an input port to an output port.

[0018] Another object of the present invention is to provide a method for designing an Ethernet switch fabric controller requiring output port buffer unit of less capacity (output port buffer unit of smaller length) while still working with an Ethernet switch to smoothly forward the packet from an input port to an output port.

[0019] A further object of the present invention is to provide an Ethernet switch fabric controller requiring less logic gates while still working with an Ethernet switch to smoothly forward the packet from an input port to an output port.

[0020] Another further object of the present invention is to provide a method for designing an Ethernet switch fabric controller composed of circuits of smaller size while still working with an Ethernet switch to smoothly forward the packet from an input port to an output port.

[0021] The present invention is characterized in that at least one temporary buffer unit is used to temporarily save a packet header when there's no available memory unit in the output port buffer unit corresponding to the packet header given that the length of the output port buffer unit is smaller than the number of input ports of the Ethernet switch.

[0022] An aspect of the present invention is a device for processing the forwarding of the packet header received by each input port of an Ethernet switch to an output port buffer unit, thereupon the Ethernet switch switches (or forwards) the packet at each input port to an output port according to the packet header in each output port buffer unit. Assume the Ethernet switch comprises M input ports and Q output ports. The device thus suggested by the present invention comprises:

[0023] Q output port buffer units each of length N;

[0024] J temporary buffer units each of length K, where J and K being integers; and

[0025] a processor possibly embodied by a CPU or logic circuit for forwarding the packet header received by the input port to a corresponding output port buffer unit in case the corresponding output port buffer unit is in a first state, the corresponding output port buffer unit is one output port buffer unit corresponding to the packet header, and forwarding, in case the corresponding output port buffer unit is in a second state, the packet header to a corresponding temporary buffer unit which is one temporary buffer unit in a first state, and forwarding the packet header in the temporary buffer unit to the output port buffer unit having at least an available memory unit and corresponding to the packet header of the data packet in the temporary buffer unit. The corresponding output port buffer unit is in the first state when having at least an available memory unit therein, and is in the second state when having no available memory unit therein. The temporary buffer unit is in the first state when having at least an available memory unit therein and having no packet header which is corresponded by any output port buffer unit different from the corresponding output port buffer unit that is an output port buffer unit corresponding to the packet header currently considered for being forwarded to the temporary buffer unit, i.e., a temporary buffer unit is in the first state when having at least an available memory unit therein and each packet header therein is corresponded by the corresponding output port buffer unit (the output port buffer unit which corresponds to the packet header currently considered for being forwarded to the temporary buffer unit).

[0026] In the embodiment M is equal to Q, N is smaller than M, J is chosen to equal [(M/N)−1], and K is chosen to equal (M−N), as suggested by the present invention and explained below.

[0027] It is reasonable to have a condition that no packet header will be admitted to an input port unless the input port currently has no packet header therein or has completed the processing (forwarding to a proper temporary buffer unit or output port buffer unit) of a packet header previously received, i.e., there are at most 32 packet headers in an Ethernet switch fabric controller if there are 32 input ports in the Ethernet switch working with the Ethernet switch fabric controller, for example.

[0028] Let's first consider the length of the temporary buffer unit. Assume the number of input ports is M and the length of output port buffer unit is N (here N<M), the worst case is that the destination output port buffer unit (corresponding output port buffer unit) of the packet header in each of the N input ports is the same at one time, resulting in the need of forwarding N packet headers to the destination output port buffer unit and forwarding (M−N) packet headers to the same temporary buffer unit, leading to the consideration of designing the temporary buffer unit of length (M−N).

[0029] Let's now consider the number of temporary buffer units for the case that M is divisible by N. In case the number of full output port buffer units (the output port buffer unit with every memory unit therein saving a packet header) at one time is M/N, there's no need of forwarding any packet header to a temporary buffer unit. Another case is that the number of full output port buffer units is (M/N−1) while there are N requests for entering these (M/N−1) full output port buffer units at the same time (there are N packet headers waiting to be forwarded to these full output port buffer units at the same time), therefore we may choose (M/N−1) as the number of temporary buffer units each of length (M−N). It can be seen the total number of the memory units, including those [(M/N−1)*(M−N)] of all temporary buffer units and those M*N of all output port buffer units, is {M*N+[(M/N)−1]* (M−N)}. For an example of 32 input ports and 32 output ports in an Ethernet switch, a feasible configuration suggested by the present invention is that there are 32 output port buffer units each of length N, and [(M/N)−1] temporary buffer units each of length (32−N), with N to be selected for minimizing the number of memory units represented by {M*N+[(M/N)−1]* (M−N)}. The selection of N can be easily done by computation, especially by using a computer.

[0030] In case M is not divisible by N, let M/N=U+R where U is the largest integer less than the real value of MIN and R is the remainder of M/N (i.e., R is the difference value between the real value of M/N and U. and is obviously less than N), the number of temporary buffer units is U−1+[R/U] where [R/U] is the largest integer less than the real value of R/U, and the total number of memory units required is M*N+(U−1+[R/U])*(M−N).

[0031] It can be easily computed that the relatively smaller number of memory units totally required is 324, 295, 296, 324, and 328 respectively for N=4, N=5, N=6, N=7, N=8 in case M=32. Because the overflow probability of output port buffer for N=8is lower than that N=4, N=5, N=6, and N=7, 8 is selected to be the length of each of the 32 output port buffer units, and the number of temporary buffer units is 3, leading to the need of only 324 of total memory units, reducing 68.36 percent of memory capacity demand compared to the conventional system where 32*32=1024 memory units are required.

[0032] The above processor according to the present invention may comprise: a retrieving controller, and a contention resolution controller; the retrieving controller forwards the packet header from the input port to the contention resolution controller, the contention resolution controller checks if the corresponding output port buffer unit is in the first state, and forwards the packet header to the corresponding output port buffer unit in case the corresponding output port buffer unit is in the first state, while forwards the packet header to the corresponding temporary buffer unit after identifying the corresponding temporary buffer unit among the temporary buffer units. For example, a temporary buffer unit in the first state (a temporary buffer unit having at least an empty memory unit therein, and with each packet header saved therein being corresponded by the destination output port buffer unit of the packet header currently considered for being forwarded, i.e., a temporary buffer unit having at least an empty memory unit therein, and with each packet header saved therein having the same destination output port buffer unit as that of the packet header considered for being forwarded, or a temporary buffer unit having at least an empty memory unit therein, and with each packet header saved therein corresponded by an output port buffer unit which corresponds to the packet header currently considered for being forwarded) is identified to be the corresponding temporary buffer unit for the packet header.

[0033] The above processor may further comprise a temporary buffer unit controller for checking if the output port buffer unit corresponding to the packet header in the temporary buffer unit has at least an available memory unit, and for forwarding the packet header in the temporary buffer unit to the output port buffer unit which corresponds to the packet header in the temporary buffer unit and has at least an available memory unit.

[0034] The above retrieving controller is a sequential polling controller polling each input port cyclically to forward the packet header from the input port to the contention resolution controller.

[0035] The above processor further comprises a plurality of command interpreters each associated with one input port, and in a busy state when a packet header is received thereat the associated input port to wait for being forwarded to the contention resolution controller, and wherein the retrieving controller recognizes the busy state to forward the packet header at the associated input port which is in the busy state to the contention resolution controller.

[0036] Another aspect of the present invention is a device for processing the forwarding of the packet header received by each input port of an Ethernet switch to an output port buffer unit of length N, the Ethernet switch comprises M input ports and Q output ports, N is less than M, the number of the output port buffer units is L which may or may not be equal to Q, the device comprises:

[0037] J temporary buffer units each of length K, where J and K being integers; and

[0038] a processor comprising a plurality of P retrieving controllers assigned to respectively correspond to different groups of the input ports, where P being an integer larger than one;

[0039] each of the retrieving controllers forwarding the packet header received by the corresponded group of the input ports to the processor, in case the corresponding output port buffer units of the packet headers forwarded by the retrieving controllers to the processor are different from each other, the processor respectively sends the packet headers to the output port buffer units respectively corresponding to the packet headers and having at least an available memory unit, and in case the corresponding output port buffer units of the packet headers forwarded by the retrieving controllers are not different from each other, the processor sends the packet headers having the same corresponding output port buffer units, in the order according to the timestamps representing the time of receiving the packet headers by the input ports, to the same corresponding output port buffer units having at least an available memory unit, while in case the corresponding output port buffer units having no available memory unit, the processor sends the packet headers to the temporary buffer units in a first state after identifying the temporary buffer units in the first state among all the temporary buffer units, the processor sends the packet header in the temporary buffer units to the output port buffer units which respectively correspond to the packet headers in the temporary buffer units and have at least an available memory unit.

[0040] The processor according to another aspect of the present invention aforementioned further comprises: a contention resolution controller; and a temporary buffer unit controller; each of the retrieving controllers forwarding the packet headers received by the corresponded group of the input ports to the contention resolution controller, in case the corresponding output port buffer units of the packet headers forwarded by the retrieving controllers are different from each other, the contention resolution controller sends the packet headers to the output port buffer units respectively corresponding to the packet headers and having at least an available memory unit, and in case the corresponding output port buffer units of the packet headers forwarded by the retrieving controllers are not different from each other, the contention resolution controller sends the packet headers having the same corresponding output port buffer unit, in the order according to the timestamps representing the time of receiving the packet headers by the input ports, to the same corresponding output port buffer unit having at least an available memory unit, while in case the corresponding output port buffer unit has no available memory unit, the contention resolution controller sends the packet headers to the temporary buffer unit in the first state after identifying the temporary buffer unit in the first state among the temporary buffer units; the temporary buffer unit controller sends the packet headers in the temporary buffer units to the corresponding output port buffer units (the output port buffer units which respectively correspond to the packet headers in the temporary buffer units) having at least an available memory unit.

[0041] An algorithm aspect of the present invention is a process for forwarding the packet header received by each input port of an Ethernet switch to an output port buffer unit of length N, the Ethernet switch comprises M input ports and Q output ports, the number of the output port buffer units is L which may be selected so as to equal Q, the process comprises the steps of:

[0042] (a). recognizing the packet header received by the input port (another way is retrieving the packet header from the input port);

[0043] (b). identifying the output port buffer unit which corresponds to the packet header as a destination output port buffer unit;

[0044] (c). checking if the destination output port buffer unit has at least an available memory unit;

[0045] (d). in case there is at least an available memory unit in the destination output port buffer unit, forwarding the packet header from the input port to the destination output port buffer unit;

[0046] (e). in case there is no available memory unit in the destination output port buffer unit, forwarding the packet header from the input port to the temporary buffer unit which is in a first state;

[0047] (f). whenever one corresponding output port buffer unit, which is one output port buffer unit corresponding to the packet header in the temporary buffer unit, has at least an available memory unit, forwarding the packet header in the temporary buffer unit to the corresponding output port buffer unit.

[0048] The above temporary buffer unit is in the first state when having at least an available memory unit and having no packet header therein corresponded by one output port buffer unit different from the destination output port buffer unit.

[0049] Another aspect of the above temporary buffer unit is that it is in the first state when having at least an available memory unit therein and the destination output port buffer unit corresponds to each packet header therein.

[0050] The above process further comprises a step of computing the J, and the K, so that the J is equal to [(M/N)−1], and the K is equal to (M−N), where N is computed so as to reduce the number of logic gates (memory units) constituting all the output port buffer units and the temporary buffer units, while the process can still avoid the overflow possibly caused by the fact that the length of the output port buffer unit is less than the number M of the input ports.

[0051] Another algorithm aspect of the present invention is a process for forwarding the packet header received by each input port of an Ethernet switch to an output port buffer unit of length N, the Ethernet switch comprises M input ports divided into P groups and Q output ports, the N is less than the M, the process comprises the steps of:

[0052] (a). simultaneously applying pooling in each of the groups for recognizing, one by one, the packet headers received by the input ports in each of the groups;

[0053] (b). identifying destination output port buffer units among the output port buffer units, the destination output port buffer units are the output port buffer units which respectively correspond to the recognized packet headers;

[0054] (c). in case the destination output port buffer units are different from each other, respectively sending the recognized packet headers to the destination output port buffer units having at least an available memory unit, and in case the destination output port buffer units are not different from each other, sending the recognized packet headers corresponded by the same destination output port buffer unit, in the order according to the timestamps representing the time of receiving the packet headers by the input ports, to the same the destination output port buffer unit which has at least an available memory unit, while in case the destination output port buffer unit has no available memory unit, sending the packet headers to the temporary buffer units in a first state after identifying the temporary buffer units in the first state among all of the temporary buffer units, the temporary buffer units in the first state are the temporary buffer units which have at least an available memory unit and have the packet headers therein corresponded by the destination output port buffer unit.

[0055] (d). sending the packet header in the temporary buffer unit to the destination output port buffer unit (one output port buffer unit which corresponds to the packet header in the temporary buffer unit) having at least an available memory unit.

[0056] The above process may also comprise a step of computing the number J of the temporary buffer units, and the length K of each of the temporary buffer units, so that the J is equal to [(M/N)−1], and the K is equal to (M−N), where N is computed so as to minimize the total capacity (number of memory units or logic gates) of all buffer including the temporary buffer units and the output port buffer units, while the process can still avoid the overflow possibly caused by the fact that the length of the output port buffer unit is less than the number M of the input ports.

[0057] Another further algorithm aspect of the present invention is a process for forwarding the packet header received by each input port of an Ethernet switch to an output port buffer unit of length N, the Ethernet switch comprises M input ports in P groups and Q output ports, the number L of the output port buffer units may be so selected that the L is equal to the Q, the process comprising the steps of:

[0058] (a). simultaneously applying pooling in each of the groups for retrieving, one in one time interval, the packet headers received by the input ports in each of the groups;

[0059] (b). identifing destination output port buffer units among the output port buffer units, the destination output port buffer units are the output port buffer units which respectively correspond to the retrieved packet headers;

[0060] (c). in case the destination output port buffer units are different from each other, respectively sending the packet headers retrieved from the input ports to the destination output port buffer units having at least an available memory unit, and in case the destination output port buffer units are not different from each other, sending the packet headers which have been retrieved from the input ports and which are corresponded by the same destination output port buffer unit, in the order according to the timestamps representing the time of receiving the packet headers by the input ports, to the same destination output port buffer unit which has at least an available memory unit, while in case the destination output port buffer unit has no available memory unit, sending the packet headers retrieved from the input ports to the temporary buffer units in a first state after identifying the temporary buffer units in the first state among all of the temporary buffer units, the temporary buffer units in the first state are the temporary buffer units which respectively correspond to the retrieved packet headers and have at least an available memory.

[0061] (d). sending the packet header in the temporary buffer unit to the destination output port buffer unit (one output port buffer unit which corresponds to the packet header in the temporary buffer unit) having at least an available memory unit.

[0062] The another algorithm aspect of the present invention is a process for forwarding the packet header received by each input port of an Ethernet switch to an output port buffer unit of length N, the Ethernet switch comprises M input ports and Q output ports, the number of the output port buffer units may be selected to equal the Q, the process comprises the steps of:

[0063] (a). separating (or dividing) M input ports into at least two groups;

[0064] (b). simultaneously applying pooling in each of the groups for recognizing, one in one time interval, the packet headers received by the input ports in each of the groups;

[0065] (c). identifying destination output port buffer units among the output port buffer units, the destination output port buffer units are the output port buffer units which respectively correspond to the recognized packet headers;

[0066] (d). in case the destination output port buffer units are different from each other, respectively sending the recognized packet headers to the destination output port buffer units having at least an available memory unit, and in case the destination output port buffer units are not different from each other, sending the recognized packet headers corresponded by the same destination output port buffer unit, in the order according to the timestamps representing the time of receiving the packet headers by the input ports, to the same the destination output port buffer unit which has at least an available memory unit, while in case the destination output port buffer unit has no available memory unit, sending the packet headers to the temporary buffer units in a first state after identifying the temporary buffer units in the first state among all of the temporary buffer units, the temporary buffer units in the first state are the temporary buffer units which have an available memory unit and have the packet headers therein corresponded by the destination output port buffer unit.

[0067] (e). sending the packet header in the temporary buffer unit to the destination output port buffer unit (one output port buffer unit which corresponds to the packet header in the temporary buffer unit) having at least an available memory unit.

[0068] Again the above process may also comprise a step of computing the number J of the temporary buffer units, and the length K of each of the temporary buffer units, so that the J is equal to [(M/N)−1], and the K is equal to (M−N), where N is computed so as to minimize the total capacity (number of memory units or logic gates) of all buffer including the temporary buffer units and the output port buffer units, while the process can still avoid the overflow possibly caused by the fact that the length of the output port buffer unit is less than the number M of the input ports.

[0069] The present invention may best be understood through the following description with reference to the accompanying drawings, in which:

[0070] FIG. 1 shows a conventional Ethernet switch fabric controller.

[0071] FIG. 2 shows a system for an embodiment of the present invention for replacing a conventional Ethernet switch fabric controller.

[0072] FIG. 3 illustrates a table for computing the optimum length of an output port buffer unit in the embodiment shown in FIG. 2 for an example where N=32.

[0073] FIG. 4 shows a system for another embodiment of the present invention for replacing a conventional Ethernet switch fabric controller.

[0074] FIG. 5 illustrates a table for computing the optimum length of an output port buffer unit in the embodiment shown in FIG. 4 for an example where there are 64 input ports.

[0075] An embodiment of the present invention is a device shown in FIG. 2 for processing the forwarding of the packet header received by each input port of an Ethernet switch to an output port buffer unit, thereupon the Ethernet switch switches (or forwards) the packet at each input port to an output port according to the packet header in the output port buffer unit. Assume the Ethernet switch comprises 32 input ports (input port 1, input port 2 . . . , input port 32) each denoted by 3 (reference numeral) in the figure, and 32 output ports (output port 1, output port 2 . . . , output port 32) each denoted by 5 (reference numeral) in the figure. The device thus suggested by the present invention comprises:

[0076] an output port buffer block 11 including 32 output port buffer units 111 (output port buffer unit 1, output port buffer unit 2, . . . , output port buffer unit 32) each of length N;

[0077] a temporary buffer block 12 including J of temporary buffer units 121 (temporary buffer unit 1, temporary buffer unit 2, . . . , temporary buffer unit j) each of length K, where J and K being integers; and

[0078] a processor 15 possibly embodied by a CPU or logic circuit for forwarding the packet header received by an input port to a corresponding output port buffer unit in case the corresponding output port buffer unit is in a first state, the corresponding output port buffer unit is one output port buffer unit corresponding to the packet header, and forwarding, in case the corresponding output port buffer unit is in a second state, the packet header to a corresponding temporary buffer unit which is one temporary buffer unit in a first state, and forwarding the packet header in the temporary buffer unit to the output port buffer unit having at least an available memory unit and corresponding to the packet header in the temporary buffer unit. The corresponding output port buffer unit is in the first state when having at least an available memory unit therein, and is in the second state when having no available memory unit therein. A temporary buffer unit is in the first state when having at least an available memory unit therein and having no packet header therein which is corresponded by any output port buffer unit different from the corresponding output port buffer unit that is an output port buffer unit corresponding to the packet header currently considered for being forwarded to the temporary buffer unit, i.e., a temporary buffer unit is in the first state when having at least an available memory unit therein and each packet header therein is corresponded by the corresponding output port buffer unit (the output port buffer unit which corresponds to the packet header currently considered for being forwarded to the temporary buffer unit). In other words, a temporary buffer unit is in the first state when having at least an available memory unit therein and each packet header therein has the same destination output port buffer unit.

[0079] In the embodiment N is smaller than the number of input ports or output ports, in order to avoid the requirement of a great number of memory units for an Ethernet switch fabric controller as adopted by prior arts. Let M represent the number of input ports (or output ports), J is chosen to equal [(M/N)−1], and K is chosen to equal (M−N), as suggested by the present invention and explained below.

[0080] It is reasonable to set a condition that no packet header will be admitted to an input port unless the input port currently has no packet header therein or has completed the processing (forwarding to a proper temporary buffer unit or output port buffer unit) of a packet header previously received, i.e., there are at most 32 packet headers in an Ethernet switch fabric controller if there are 32 input ports in the Ethernet switch working with the Ethernet switch fabric controller, for example.

[0081] Let's first consider the length of the temporary buffer unit. Given the number of input ports is M and the length of output port buffer unit is N (here N<M), the worst case is that the destination output port buffer unit (corresponding output port buffer unit) of the packet header in each of the M input ports 3 is the same at one time, resulting in the need of forwarding N packet headers to their destination output port buffer unit (the same output port buffer unit, one output port buffer unit 111 shown in the figure) and forwarding (M−N) packet headers to the same temporary buffer unit (one temporary buffer unit 121 in the figure), leading to the consideration of designing the temporary buffer unit 121 of length (M−N).

[0082] Let's now consider the number of temporary buffer units 121. In case the number of full output port buffer units (the output port buffer unit with every memory unit therein saving a packet header) at one time is M/N, there's no need of forwarding any packet header to any temporary buffer unit 121. Another case is that the number of full output port buffer units is (M/N−1) while there are N requests for entering these (M/N−1) full output port buffer units at the same time (there are N packet headers waiting to be forwarded to these full output port buffer units at the same time), therefore we may choose (M/N−1) as the number of temporary buffer units each of length (M−N). It can be seen the total number of the memory units (one memory unit for saving one packet header), including those [(M/N−1)*(M−N)] of all temporary buffer units 121 and those M*N of all output port buffer units 111, is {M*N+[(M/N)−1]*(M−N)}. For an example of 32 input ports (M=32 for a particular example) and 32 output ports in an Ethernet switch, a feasible configuration suggested by the present invention is that there are 32 output port buffer units each of length N, and [(M/N)−1] temporary buffer units each of length (32−N), with N to be selected for minimizing the number of memory units represented by {M*N+[(M/N)−1]*(M−N)}.

[0083] FIG. 3 is a table showing the total number {M*N+[(M/N)−1]*(M−N)} of memory units with N ranging from 1 to M (M=32 for this particular example). It can be seen here the total number is minimum when N=5 or N=6 while the total number approximates the minimum for N=8 which is accompanied with lowest probability of incurring overflow, leading to the suggestion that N=8 is chosen, i.e., the Ethernet switch fabric controller may be designed so as to have its output port buffer unit of length 8 (the output port buffer unit has 8 memory units each for saving a packet header therein) and have M/N−1 (=32/8−1=3 for the particular example) temporary buffer units, i.e., the number of its temporary buffer units is 3, and the length of the temporary buffer unit is M−N (=32−8=24 for a particular example).

[0084] The above processor 15 according to the present invention may comprise: a retrieving controller 151, and a contention resolution controller 153; the retrieving controller 151 forwards the packet header from the input port 3 to the contention resolution controller 153, the contention resolution controller 153 checks if the corresponding output port buffer unit 111 is in the first state, and forwards the packet header to the corresponding output port buffer unit 111 in case the corresponding output port buffer unit 111 is in the first state, while forwards the packet header to the corresponding temporary buffer unit after identifying the corresponding temporary buffer unit among all the temporary buffer units 121 in temporary buffer block 12. For example, a temporary buffer unit in the first state is identified to be the corresponding temporary buffer unit for the packet header, where the temporary buffer unit in the first state is the temporary buffer unit having at least an empty memory unit therein, and with each packet header saved therein being corresponded by the destination output port buffer unit of the packet header currently considered for being forwarded, i.e., it is the temporary buffer unit having at least an empty memory unit therein, and with each packet header saved therein having the same destination output port buffer unit as that of the packet header considered for being forwarded, or a temporary buffer unit having at least an empty memory unit therein, and with each packet header saved therein corresponded by an output port buffer unit 111 which corresponds to the packet header currently considered for being forwarded.

[0085] The above processor 15 may further comprise a buffer controller 155 for checking if the output port buffer unit corresponding to the packet header in the temporary buffer unit has at least an available memory unit, and for forwarding the packet header in the temporary buffer unit to the output port buffer unit which corresponds to the packet header in the temporary buffer unit and has at least an available memory unit.

[0086] The above retrieving controller 151 is a sequential polling controller polling each input port cyclically to forward the packet header from the input port 3 to the contention resolution controller 153.

[0087] The above processor further comprises a plurality of command interpreters 157 each associated with one input port 3, and in a busy state when a packet header is received thereat the associated input port to wait for being forwarded to the contention resolution controller 153, and wherein the retrieving controller 151 recognizes the busy state to forward the packet header received at the associated input port to the contention resolution controller 153.

[0088] Another embodiment of the present invention is a device shown in FIG. 4 for processing the forwarding of packet header received by each input port 3 of an Ethernet switch to an output port buffer unit, thereupon the Ethernet switch switches (or forwards) the packet at each input port to an output port according to the packet header in each output port buffer unit. It is assumed that the Ethernet switch comprises M input ports and Q output ports, and M=64=Q for a particular example. The device may be configured to comprise:

[0089] an output port buffer block 21 including 64 output port buffer units 211 (output port buffer unit 1, output port buffer unit 2, . . . , output port buffer unit 64) each of length N;

[0090] a temporary buffer block 22 including J of temporary buffer units 221 (temporary buffer unit 1, temporary buffer unit 2, . . . ,temporary buffer unit j) each of length K, where J and K being integers; and

[0091] a processor 25 comprising a plurality of P retrieving controllers (P=2 for a particular example) 251 and 252 assigned to respectively correspond to different groups of the input ports (2 groups each comprising 32 input ports for a particular example). Obviously the number of input ports in each group is not necessarily the same. Each retrieving controller 251 or forwards the packet header received by the corresponded group of the input ports to the processor 25. In case the corresponding output port buffer units of the packet headers forwarded by the retrieving controllers 251 or 252 to the processor 25 are different from each other, the processor 25 respectively sends the packet headers to the output port buffer units respectively corresponding to the packet headers of the packet header and having at least an available memory unit, and in case the corresponding output port buffer units of the packet headers forwarded by the retrieving controllers 252 and 251 are not different from each other, the processor 25 sends the packet headers having the same corresponding output port buffer units, in the order according to the timestamps representing the time of receiving the packet headers by the input ports, to the same corresponding output port buffer units having at least an available memory unit, while in case the corresponding output port buffer units having no available memory unit, the processor 25 sends the packet headers to the temporary buffer units 221 in a first state after identifying the temporary buffer units in the first state from among all the temporary buffer units in temporary buffer block 22; processor 25 sends the packet header in temporary buffer units 221 to the output port buffer units which respectively correspond to the packet headers of the packet headers in the temporary buffer units 221 and have at least an available memory unit.

[0092] The above processor 25 further comprises: a contention resolution controller 253 and a buffer controller 255. Each retrieving controller 251 or 252 forwards the packet headers received by the corresponded group of the input ports to the contention resolution controller 253, in case the corresponding output port buffer units 211 of the packet headers forwarded by the retrieving controllers 251 and 152 are different from each other, the contention resolution controller 253 sends the packet headers to the output port buffer units 211 respectively corresponding to the packet headers and having at least an available memory unit, and in case the corresponding output port buffer units 211 of the packet headers forwarded by the retrieving controllers 251 and 252 are not different from each other, the contention resolution controller 253 sends the packet headers having the same corresponding output port buffer unit, in the order according to the timestamps representing the time of receiving the packet headers by the input ports, to the same corresponding output port buffer unit having at least an available memory unit (whenever the same corresponding output port buffer unit has at least an available memory unit), while in case the corresponding output port buffer unit has no available memory unit, the contention resolution controller 253 sends the packet headers to the temporary buffer unit in the first state after identifying the temporary buffer unit in the first state from among all the temporary buffer units in temporary buffer block 22; the buffer controller 255 sends the packet headers in the temporary buffer units 221 to the corresponding output port buffer units (the output port buffer units 211 which respectively correspond to the packet headers in the temporary buffer units 121) having at least an available memory unit.

[0093] The above processor 25 according to the present invention may have its contention resolution controller 253 comprise a check-packet module 2531 and a check-BUFFER module 2532; the check-packet module 2531 checks if the corresponding output port buffer units 211 of the packet headers forwarded by the retrieving controllers 251 and 252 are different from each other, and sends the packet headers to the check-BUFFER module 2532 in case the corresponding output port buffer units 211 of the packet headers forwarded by the retrieving controllers 251 and 252 are different from each other, while compares, in case the corresponding output port buffer units 211 of the packet headers forwarded by the retrieving controllers 251 and 252 are not different from each other, the timestamps (each timestamp for indicating the time of receiving a packet header at an input port) of the packet headers having the same corresponding output port buffer unit 211, and sends the packet headers to the check-BUFFER module 2532 in the order according to the timestamps, the check-BUFFER module 2532 checks if the corresponding output port buffer unit 211 has at least an available memory unit, and sends the packet header to the corresponding output port buffer unit in case the corresponding output port buffer unit has at least an available memory unit, while sends the packet header to a temporary buffer unit 221 in the first state in case the corresponding output port buffer unit has no available memory unit; the buffer controller 255 recognizes the packet headers in the temporary buffer units 221, and checks if the output port buffer units 211 which respectively correspond to the packet headers have at least an available memory unit, and sends the packet headers in the temporary buffer units 221 to the output port buffer units 211 which respectively correspond to the packet headers and have at least an available memory unit.

[0094] The above retrieving controller 251 and 252 may be sequential polling controllers respectively and cyclically polling their corresponded groups of the input ports 3 to forward the packet header from the corresponded group of input ports to the contention resolution controller 253.

[0095] The above processor 25 may further comprise a plurality of command interpreters (32 of command interpreters 257 and 32 of command interpreters, for a particular example) each associated with one input port and in a busy state when a packet header is received thereat the associated input port to wait for being forwarded to the contention resolution controller 253, and the retrieving controller 251 and 252 simultaneously pool (cyclically inquire each among a group) their respectively corresponded groups by recognizing the busy state of the command interpreters 257 and 258 respectively associated with each input port in their corresponded groups, to forward the packet header at the associated input port to the contention resolution controller 253.

[0096] The same as the aforementioned relevant explanation, here J is chosen to equal [(M/N)−1], and K is chosen to equal (M−N), and the total number of all memory units is {M*N+[(M/N)−1]*(M−N)}.

[0097] FIG. 5 is a table showing the total number {M*N+[(M/N)−1]*(M−N)} of memory units with N ranging from 1 to M (M=64 for this particular example). It can be seen here the total number is minimum when N=8, leading to the suggestion that N=8 is chosen, i.e., the Ethernet switch fabric controller may be designed so as to have its output port buffer unit of length 8 (the output port buffer unit has 8 memory units each for saving a packet header therein) and have M/N−1 (=64/8−1=7 for the particular example) temporary buffer units, i.e., the number of its temporary buffer units is 7, and the length of the temporary buffer unit is M−N (=64−8=56 for the particular example).

[0098] A further aspect of the present invention is a process for forwarding the packet header received by each input port of an Ethernet switch to an output port buffer unit, thereupon the Ethernet switch switches (or forwards) the packet at each input port to an output port according to the packet header in each output port buffer unit. It is assumed here that the Ethernet switch comprises M input ports and M (M is not necessarily equal to Q) output ports, and the number of output port buffer units is M, each output port buffer unit is of length N. The process comprises, referring to the system shown in FIG. 2, the steps of:

[0099] (a). recognizing the packet header received by the input port (another alternative is retrieving the packet header from the input port to a resolution controller and recognizing it in the resolution controller);

[0100] (b). identifying the output port buffer unit which corresponds to the recognized packet header as a destination output port buffer unit;

[0101] (c). checking if the destination output port buffer unit has at least an available memory unit;

[0102] (d). in case there is at least an available memory unit in the destination output port buffer unit, forwarding the packet header from the input port to the destination output port buffer unit;

[0103] (e). in case there is no available memory unit in the destination output port buffer unit, forwarding the packet header from the input port to a temporary buffer unit which is in a first state;

[0104] (f). whenever one corresponding output port buffer unit, which is one output port buffer unit 111 corresponding to the packet header in the temporary buffer unit, has at least an available memory unit, forwarding the packet header in the temporary buffer unit to the corresponding output port buffer unit 111.

[0105] For the above process, the temporary buffer unit is in the first state when having at least an available memory unit and having no packet header therein corresponded by one output port buffer unit 211 different from the destination output port buffer unit of the recognized packet header currently to be forwarded to the temporary buffer unit. In other words, the temporary buffer unit is in the first state when having at least an available memory unit therein and the destination output port buffer unit of the recognized packet header currently to be forwarded thereto corresponds to each packet header therein.

[0106] The above process further comprises a step of computing the number J of the tbus, and the length K of the tbu, so that the J is equal to [(M/(N)−1], and the K is equal to (M−N), and N is computed so as to reduce the number of memory units, thereby reduce the number of logic gates constituting all the output port buffer units 211 and the temporary buffer units 221.

[0107] The above process further comprises, before step (a), a step of detecting the packet header received by each input port 3.

[0108] The above step (e) comprises the steps of: in case there is no available memory unit in the destination output port buffer unit, identifying one temporary buffer unit in the first state from among all the temporary buffer units in temporary buffer block 12 as a destination temporary buffer unit, forwarding the packet header from the input port to the destination temporary buffer unit.

[0109] The above step (f) comprises the steps of:

[0110] (f-1). recognizing the packet header in each temporary buffer unit 221;

[0111] (f-2). identifying the output port buffer unit which corresponds to the packet header in the temporary buffer unit as a temp-to-destination output port buffer unit;

[0112] (f-3). checking if the temp-to-destination output port buffer unit has at least an available memory unit;

[0113] (f-4). in case there is at least an available memory unit in the temp-to-destination output port buffer unit, forwarding the packet header from the temporary buffer unit to the temp-to-destination output.

[0114] Another algorithm aspect of the present invention is a process for forwarding, in a system such as that shown in FIG. 4, the packet header received by each input port 3 of an Ethernet switch 2, to an output port buffer unit 211 of length N, the Ethernet switch 2 comprises M input ports in P groups, and Q output ports, the number of output port buffer units 211 is Q, the process comprises the steps of:

[0115] (a). simultaneously applying pooling in each of the groups for recognizing, one by one, the packet headers received by the input ports 3 in each of the groups;

[0116] (b). identifying destination output port buffer units among the output port buffer units 211, the destination output port buffer units being the output port buffer units 211 which respectively correspond to the recognized packet headers;

[0117] (c). in case the destination output port buffer units are different from each other, respectively sending the recognized packet headers to the destination output buffer units having at least an available memory unit, and respectively sending the recognized packet header to a temporary buffer unit in a first state when the destination output port unit has no available memory unit, while in case the destination output port buffer units are not different from each other, sending the recognized packet headers corresponded by the same destination output port buffer unit, in the order according to the timestamps representing the time of receiving the recognized packet headers by the input ports 3, to the same destination output port buffer unit which has at least an available memory unit, and sending the recognized packet headers to the temporary buffer units which are in the first state when the destination output port buffer unit has no available memory unit.

[0118] (d). sending the packet header in the temporary buffer unit 221 to the destination output port buffer unit (one output port buffer unit 211 which corresponds to the packet header in the temporary buffer unit 221) having at least an available memory unit, i.e., sending the packet header in the temporary buffer unit 221 to one of the output port buffer unit 211 which corresponds to the packet header in the temporary buffer unit 221 and has at least an available memory unit.

[0119] The above step (c) comprises the step of identifying the temporary buffer unit in the first state from among the temporary buffer units 221, the temporary buffer unit in the first state is one of the temporary buffer units 221 which has an available memory unit and has no packet header therein corresponded by an output port buffer unit 211 that is different from the destination output port buffer unit of the recognized packet header to be forwarded thereto. In other words, the temporary buffer unit in the first state is one of the temporary buffer units 221 which has an available memory unit and has each packet header therein corresponded by the destination output port buffer unit of the recognized packet header to be forwarded thereto, i.e., the temporary buffer unit in the first state is one of the temporary buffer units 221 which has an available memory unit and has each packet header therein corresponded by the output port buffer unit corresponding to the recognized packet header to be forwarded thereto.

[0120] The above step (c) may also be embodied to comprise the steps of:

[0121] (c-1). checking if each of the destination output port buffer units has at least an available memory unit;

[0122] (c-2). in case the destination output port buffer units are different from each other, respectively sending the recognized packet headers to the destination output port buffer units having at least an available memory unit, and respectively sending the recognized packet header to a temporary buffer unit in a first state when the destination output port unit has no available memory unit, while in case the destination output port buffer units are not different from each other, sending the recognized packet headers corresponded by the same destination output port buffer unit, in the order according to the timestamps representing the time of receiving the recognized packet headers by the input ports 3, to the same destination outputport buffer unit which has at least an available memory unit, and sending the recognized packet header to one of the temporary bufferunits 221 which is in the first state unit when the destination output port buffer unit of the recognized packet header has no available memory unit.

[0123] The above step (d) comprises the steps of:

[0124] (d-1). checking the packet header in each temporary buffer unit 221;

[0125] (d-2). identifing, among the output port buffer units 211, the destination output port buffer unit of the packet header in each temporary buffer 221;

[0126] (d-3). checking if the destination output port buffer unit has at least an available memory unit;

[0127] (d-4). sending the packet header in the temporary buffer unit 221 to the destination output port buffer unit which has at least an available memory unit.

[0128] Based on the same algorithm as that for the above process embodiment, the process here also comprises a step of computing the J, and the K, so that the J is equal to [(M/N)−1], and the K is equal to (M−N), and a step of computing the N which reduces the number of memory units in order to reduce the logic gates constituting all the output port buffer units 211 and the temporary buffer units 221.

[0129] The above step (a) comprises one step of producing a busy state signal at each input port 3 in response to a packet header received thereat, for enabling the packet header at each input port 3 to be recognized right after it is received by the input port 3.

[0130] The other algorithm aspect of the present invention is a process for forwarding, in the system such as that shown in FIG. 4, the packet header received by each input port 3 of an Ethernet switch 2 to an output port buffer unit 211 of length N, the Ethernet switch 2 comprises M input ports in P groups, and Q output ports, the number of output port buffer units 211 is Q, the process comprises the steps of:

[0131] (a). simultaneously applying pooling in each of the groups for retrieving, one in one time interval, the packet headers received by the input ports 3 in each of the groups;

[0132] (b). identifying destination output port buffer units among the output port buffer units 211, the destination output port buffer units 211 being the output port buffer units 211 which respectively correspond to the retrieved packet headers;

[0133] (c). in case the destination output port buffer units are different from each other, respectively sending the retrieved packet headers to the destination output buffer units having at least an available memory unit, and respectively sending the retrieved packet header to a temporary buffer unit in a first state when the destination output port unit has no available memory unit, while in case the destination output port buffer units are not different from each other, sending the retrieved packet headers corresponded by the same destination output port buffer unit, in the order according to the timestamps representing the time of receiving the retrieved packet headers by the input ports 3, to the same destination output port buffer unit which has at least an available memory unit, and sending the retrieved packet header to one of temporary buffer units 221 which is in the first state when the destination output port buffer unit has no available memory unit.

[0134] (d). sending the packet header in the temporary buffer unit to the destination output port buffer unit (one output port buffer unit 211 which corresponds to the packet header in the temporary bufferunit 221) having at least an available memory unit, i.e., sending the packet header in the temporary buffer unit 221 to one of the output port buffer unit 211 which corresponds to the packet header in the temporary buffer unit 221 and has at least an available memory unit.

[0135] There is still another algorithm aspect of the present invention wherein a process is embodied for forwarding, in the system such as that shown in FIG. 4, the packet header received by each input port 3 of an Ethernet switch 2 to an output port buffer unit 211 of length N, the Ethernet switch 2 comprises M of input ports, and Q output ports, the number of output port buffer units 211 is M, the process comprises the steps of:

[0136] (a). separating(or dividing) the M input ports into at least two groups;

[0137] (b). simultaneously applying pooling in each of the groups for recognizing, one in one time interval, the packet headers received by the input ports 3 in each of the groups;

[0138] (c). identifying destination output port buffer units 211 among the output port buffer units 211, the destination output port buffer units 211 being the output port buffer units 211 which respectively correspond to the recognized packet headers;

[0139] (d). in case the destination output port buffer units are different from each other, respectively sending the recognized packet headers to the destination output buffer units having at least an available memory unit, and respectively sending the recognized packet header to a temporary buffer unit in a first state when the destination output port unit has no available memory unit, while in case the destination output port buffer units are not different from each other, sending the recognized packet headers corresponded by the same destination output port buffer unit, in the order according to the timestamps representing the time of receiving the recognized packet headers by the input ports 3, to the same destination output port buffer unit which has at least an available memory unit, and sending the recognized packet header to one of temporary buffer units 221 which is in the first state when the destination output port buffer unit has no available memory unit.

[0140] (e). sending the packet header in the temporary buffer unit 221 to the destination output port buffer unit (one output port buffer unit 211 which corresponds to the packet header in the temporary buffer unit 221) having at least an available memory unit, i.e., sending the packet header in the temporary buffer unit 221 to one of the output port buffer unit 211 which corresponds to the packet header in the temporary buffer unit 221 and has at least an available memory unit.

[0141] Again Based on the same algorithm as that for the above process embodiment, the process here also comprises a step of computing the J, and the K, so that the J is equal to [(M/N)−1], and the K is equal to (M−N), and a step of computing the N which reduces the number of memory units in order to reduce the logic gates constituting all the output port buffer units 211 and the temporary buffer units 221.

[0142] While the invention has been described in terms of what are presently considered the most practical and preferred embodiments, it shall be understood that the invention is not limited to the disclosed embodiments. On the contrary, it is intended to cover various modifications and similar arrangements included within the spirit and scope of the claims which are to be accorded with the broadest interpretation so as to encompass all modifications and similar structures.