Method of dynamically renumbering ports and an apparatus thereof

Embodiments of the apparatus of dynamically renumbering ports relate to a network chip that minimizes the total logic on the network chip by limiting the number of states that needs to be preserved for all ports on the network chip. Each pipe on the network chip implements a dynamic port renumbering scheme that dynamically assigns a relative port number for each port assigned to that pipe. The dynamic port renumbering scheme allows for internal parallelism without increasing the total amount of state space required for the ports on the network chip.

FIELD OF INVENTION

The present invention relates to network chips. In particular, the present invention relates to a method of dynamically renumbering ports and an apparatus thereof.

BACKGROUND OF THE INVENTION

As network chips evolve, the need for handling more and more ports has increased. Adding more ports in a network chip often requires internal parallelism, where a portion of the traffic from each port is handled on a separate pipe. By creating more pipes, more ports can be added without causing the internal frequency of the network chip to be increased. However, increasing the number of ports inside the network chip causes problems in logic where states need to be maintained on a per port basis. For example, if the number of ports on the network chip is 128 and the number of pipes on the network chip is 8, then each pipe handles 16 of the 128 ports. Each of these ports is typically given a unique port number, which allows them to be identified. To represent these ports, an eight bit number is used. The eight bit number can represent a total of 256 ports. State space is 256 entries per pipe to store state information of 16 ports. As such, only a small subset of the state space is used. As the number of ports on a network chip increases, so does the state space per pipe. As the state space per pipe increases, so does the total logic on the network chip. It is inefficient to allocate this much state space since much of the state space is sparse.

BRIEF SUMMARY OF THE INVENTION

Embodiments of the apparatus of dynamically renumbering ports relate to a network chip that minimizes the total logic on the network chip by limiting the number of states that needs to be preserved for all ports on the network chip. Each pipe on the network chip implements a dynamic port renumbering scheme that dynamically assigns a relative port number for each port assigned to that pipe. The dynamic port renumbering scheme allows for internal parallelism without increasing the total amount of state space required for the ports on the network chip.

In one aspect, a method of a network chip is provided. The network chip includes N ports and P pipes. The method includes receiving traffic, and utilizing a dynamic port renumbering scheme by each of the P pipes to renumber each of the N ports associated with that pipe such that hardware implemented on the network chip to preserve state information for the N ports is limited.

In some embodiments, each of the P pipes handles traffic from M ports of the N ports. In some embodiments, each of the P pipes uses M relative port numbers in the dynamic port renumbering scheme. In some embodiments, M is the ceiling of N/P.

In some embodiments, utilizing a dynamic port renumber scheme includes, for each of the P pipes, assigning one of M relative port numbers to each of M ports associated with that pipe, storing all of the assignments of relative port numbers to the M ports, and maintaining all states of the M ports using the M relative port numbers.

In some embodiments, assigning one of M relative port numbers includes determining whether renumbering of one of the M ports is completed, based on the determination that the renumbering of that port is completed, using the relative port number previously assigned to that port, and based on the determination that the renumbering of that port is not completed, assigning an unused relative port number of the M relative port numbers to that port.

In some embodiments, the dynamic port renumbering scheme is a self-learning scheme.

In another aspect, a method of a network chip is provided. The network chip includes N ports and P pipes. The method includes, for each of the P pipes, handling traffic from M ports of the N ports, wherein M is the ceiling of N/P, maintaining no more than state space necessary for the M ports, and assigning one of M relative port numbers to each of the M ports. In some embodiments, the one of the M relative port numbers has not yet been used prior to the assignment.

In some embodiments, assigning one of M relative port numbers to each of the M ports includes receiving traffic, identifying one of the M ports that the traffic is from, and determining whether that port had previously been assigned a relative port number.

In some embodiments, the method also includes based on the determination that that port has not yet been assigned a relative port number, assigning an unused relative port number of the M relative port numbers to that port.

In some embodiments, the method also includes storing all of the assignments of the M relative port numbers to the M ports, and maintaining all states of the M ports using the M relative port numbers.

In yet another aspect, a network chip is provided. The network chip includes N ports and P pipes to handle traffic from the N ports. Each of the P pipes handles traffic from M ports of the N ports. Each of the P pipes uses M relative port numbers in the dynamic port renumbering scheme. Typically, M is the ceiling of N/P.

The network chip also includes a dynamic port renumbering scheme utilized by each of the P pipes to renumber each of the N ports associated with that pipe such that hardware implemented on the network chip to preserve state information for the N ports is limited.

In some embodiments, the dynamic port renumbering scheme, for each of the P pipes, assigns one of M relative port numbers to each of M ports associated with that pipe, stores all of the assignments of relative port numbers to the M ports, and maintains all states of the M ports using the M relative port numbers.

In some embodiments, one of M relative port numbers is assigned based on whether renumbering of one of the M ports that incoming traffic is from is completed. In some embodiments, based on the renumbering of that port being completed, the relative port number previously assigned to that port is used. In some embodiments, based on the renumbering of that port being not completed, an unused relative port number of the M relative port numbers is assigned to that port.

In yet another aspect, a network chip is provided. The network chip includes N ports and P pipes. Each of the P pipes handles traffic from M ports of the N ports, wherein M is the ceiling of N/P, maintains no more than state space necessary for the M ports, and assigns one of M relative port numbers to each of the M ports. In some embodiments, the one of the M relative port numbers has not yet been used prior to the assignment.

In some embodiments, each of the P pipes further receives traffic, identifies one of the M ports that the traffic is from, and determines whether that port had previously been assigned a relative port number.

In some embodiments, based on the determination that that port has not yet been assigned a relative port number, the pipe assigns an unused relative port number of the M relative port numbers to that port.

In some embodiments, each of the P pipes further stores all of the assignments of the M relative port numbers to the M ports and maintains all states of the M ports using the M relative port numbers.

In yet another aspect, a network switch is provided. The network switch includes a plurality of switch ports and at least one network chip. The at least one network chip includes N chip ports and P pipes. Typically, the N chip ports are mapped to the plurality of switch ports. Typically, the P pipes utilize a dynamic port renumbering scheme that learns from previous assignments which relative port number to assign to each of P pipes.

In some embodiments, the dynamic port renumbering scheme is implemented by each of the P pipes.

In some embodiments, each of the P pipes handles traffic from M of the N chip ports, wherein M is the ceiling of M/N.

In some embodiments, each of the P pipes determines whether an incoming port has been assigned a relative port number and based on the determination that the incoming port has not been assigned a relative port number, storing the incoming port in a storage array and assigning the incoming port an unused relative port number based on a current pointer to the storage array. In some embodiments, the determination is based on whether the incoming port is already stored in the storage array.

DETAILED DESCRIPTION OF THE INVENTION

In the following description, numerous details are set forth for purposes of explanation. However, one of ordinary skill in the art will realize that the invention can be practiced without the use of these specific details. Thus, the present invention is not intended to be limited to the embodiments shown but is to be accorded the widest scope consistent with the principles and features described herein.

Embodiments of the apparatus of dynamically renumbering ports relate to a network chip that minimizes the total logic on the network chip by limiting the number of states that needs to be preserved for all ports on the network chip. Each pipe on the network chip implements a dynamic port renumbering scheme that dynamically assigns a relative port number for each port assigned to that pipe. The dynamic port renumbering scheme allows for internal parallelism without increasing the total amount of state space required for the ports on the network chip.

Assume N ports are on a network chip and traffic from the N ports are to be handled by P pipes. It is noted that the terms pipes, buses and channels are used interchangeably herein. There is a maximum of M ports assigned to a single pipe, wherein M is the ceiling of N/P (e.g., division is rounded up). For example, if N=128 and P=8, then each pipe handles traffic from no more than 16 ports. For another example, if N=132 and P=8, then each pipe handles traffic from no more than 17 ports.

In the latter example, to represent the 132 ports, an eight bit number is used. The eight bit number can represent a total of 256 ports. However, as explained above, much of the state space of each pipe is unused since only 17 entries are used to maintain 17 port states. Rather than each pipe having state space for all 256 ports, each pipe only needs enough state space for M ports since no more than M ports are assigned to each pipe. To use just enough state space for the ports assigned to a pipe, the dynamic port renumbering scheme renumbers each port assigned to that pipe. Put differently, the dynamic port renumbering scheme dynamically assigns a relative port number to each port assigned to that pipe. These relative port numbers are thereafter used.

In some embodiments, no software is involved (e.g., no programming required). Instead, the dynamic port renumbering scheme is implemented in hardware. In some embodiments, the dynamic port renumber scheme is a self-learning scheme; the dynamic port renumbering scheme learns from previous assignments which relative port number to assign to a port that has not yet been renumbered.

Table 1 shows an exemplary pseudo-code for the dynamic port renumbering scheme.

FIG. 1illustrates a flow diagram100of the dynamic port renumbering scheme in accordance with some embodiments of the present invention. In some embodiments, the dynamic port renumbering scheme is implemented by each pipe on the network chip. Assume traffic from an incoming port is received on the pipe. The incoming port is checked with each element of an array to see if the incoming port had already been mapped to a relative port number. If there is a match, then the relative port number is based on the location in the entries array of where the match occurred. If there is no match, then the incoming is port is added to the array and is assigned a relative port number.

Referring toFIG. 1, the incoming port is checked with an ithelement of the entries array, where i is typically initialized such as to 0 (step105). If the ithelement of the entries array matches the incoming port, then the port is found (step110). A port found in the entries array indicates that the port already had been mapped to a relative port number. Typically, once mapped, the port does not need to be remapped. In some embodiments, the relative port number of that port is i.

If the ithelement of the entries array does not match the incoming port, then i is incremented by one (step115). While i is less than M where M is the ceiling of N/P (step120), then the incoming port is continuously checked with other elements of the entries array until the port is found or until i is no longer less than M. If i is no longer less than M, then the port is not found in the entries array (step125). A port not found in the entries array indicates that the port has not yet been mapped to a relative port number. The port is added to the entries array such that the next time traffic from the same port is received on the pipe, the port will be found in the entries array. In some embodiments, the relative port number assigned to that port is based on a current pointer to the entries array. After the relative port number is assigned, the current pointer is updated. In some embodiments, the current pointer is incremented by one.

FIG. 2Aillustrates a method200of the network chip in accordance with some embodiments of the present invention. The network chip includes N ports and P pipes. Each of the P pipes handles traffic from M ports of the N ports, where M is the ceiling of N/P. At a step205, traffic is received.

At a step210, a dynamic port renumbering scheme is utilized by each of the P pipes to renumber each of the N ports associated with that pipe such that hardware implemented on the network chip to preserve state information for the N ports is limited. Each of the P pipes uses M relative port numbers in the dynamic port renumbering scheme. In some embodiments, the step210includes a method discussed inFIG. 2B.

FIG. 2Billustrates the method225in accordance with some embodiments of the present invention. In some embodiments, the method225is performed for each of the P pipes. At a step230, one of M relative port numbers is assigned to each of M ports associated with the pipe. In some embodiments, the step230includes a method discussed inFIG. 2C.

FIG. 2Cillustrate the method250in accordance with some embodiments of the present invention. At a step255, it is determined whether renumbering of one of the M ports is completed.

At a step260, based on the determination that the renumbering of that port is completed, the relative port number previously assigned to that port is used.

At a step265, based on the determination that the renumbering of that port is not completed, an unused relative port number of the M relative port numbers is assigned to that port. In some embodiments, the order of the steps260and265is not critical. The steps can be performed currently or one before the other.

Returning toFIG. 2B, at a step235, all of the assignments of relative port numbers to the M ports are stored.

At a step240, all states of the M ports using the M relative port numbers are maintained.

FIG. 3Aillustrates another method300of the network chip in accordance with some embodiments of the present invention. The network chip includes N ports and P pipes. The method300is typically performed by each of the P pipes. At a step305, traffic from M ports of the N ports are handled by a pipe. Typically, M is the ceiling of N/P.

At a step310, no more than state space necessary for the M ports are maintained.

At a step315, one of M relative port numbers is assigned to each of the M ports. The one of the M relative port numbers typically has not yet been used prior to the assignment of the step315. In some embodiments, the step315includes a method discussed inFIG. 3B.

FIG. 3Billustrates the method325in accordance with some embodiments of the present invention. At a step330, traffic is received.

At a step335, one of the M ports that the traffic is from is identified.

At a step340, it is determined whether that port had previously been assigned a relative port number. Based on the determination that that port has not yet been assigned a relative port number, an unused relative port number of the M relative port numbers is assigned to that port.

All of the assignments of the M relative port numbers to the M ports are stored. And, all states of the M ports using the M relative port numbers are maintained.

Typically, the network chip is a part of a network device, such as a network switch, that is able to switch/route network traffic. The network switch includes a plurality of switch ports for receiving packets. The ports on the network chip are typically mapped to the plurality of switch ports. The network traffic is typically handled by the pipes on the network chip. In some embodiments, the network switch includes more than one network chip. The dynamic port renumbering scheme limits the number of states that needs to be preserved for all ports on the network chip, thereby advantageously minimizing the total logic on the network chip.

One of ordinary skill in the art will realize other uses and advantages also exist. While the invention has been described with reference to numerous specific details, one of ordinary skill in the art will recognize that the invention can be embodied in other specific forms without departing from the spirit of the invention. Thus, one of ordinary skill in the art will understand that the invention is not to be limited by the foregoing illustrative details, but rather is to be defined by the appended claims.