Patent Description:
Switches are hardware components of networks which control the distribution of messages or data packets based on address information contained within each data packet. A data packet can belong to a multicast group which requires the switch to replicate the packet to one or more subscribed destinations. A properly constructed switch can receive a packet on one ingress port and replicate the packet to the appropriate egress port(s) at wire or line speed, which is the maximum speed capability of a particular network.

In recent years as more and more industries rely on high performance computers and networks, a significant advantage can be extracted from minute differences in network speed and packet receipt time. Even though switches operating at line speed are capable of replicating a packet to an egress port once every clock cycle on a nanosecond scale, for multicast packets that must be replicated to multiple egress ports and/or destinations, the delay between replicating the packet to the first destination and replicating the same packet to the last destination may be significant when even just a few nanoseconds is enough to establish a competitive advantage. Specifically, because switching is generally done in a sequential order of destinations that is repeated for each packet in the multicast group, destinations at the beginning of the switching sequence will consistently benefit from a persistent bias packet-to-packet versus destinations at the end of the switching sequence, creating situations where certain ports or positions in a switching sequence are more desirable to end-users than others. In many cases end users will test networks and stress network devices, in order to determine the preferred ports and obtain an advantage over others. Multicast senders, such as financial institutions providing real-time market data to algorithmic traders, may desire systems and methods of multicast switching that reduce the packet switching bias between destinations, thereby removing any incentive for end users to test network equipment or request specific ports in the switching sequence, and ensuring the institution offers consistent service to each customer. Accordingly, there is a need for an efficient method and means for reducing the persistent bias in multicast packet replication between destinations on a switch to ensure the switch is not persistently providing material advantages to one destination over another.

<CIT> provides a fair multicast routing for a set of destinations.

Various objects, aspects, features, and advantages of the disclosure will become more apparent and better understood by referring to the detailed description taken in conjunction with the accompanying drawings, in which like reference characters identify corresponding elements throughout.

The details of various embodiments of the methods and systems are set forth in the accompanying drawings and the description below.

Claim <NUM> discloses a method of reducing bias in multicast replication.

Claim <NUM> discloses a network device for forwarding packets.

<FIG> is one example of a configuration of a network device in a network, in accordance with the present invention. The network device may be a hardware-based device such as network switch for moving data packets in a network according to address information contained within the packet itself. In some embodiments, the network device may additionally and/or alternatively perform the function of a router and be configured to move packets in and across networks, or in general any other device configured to move data in or across networks. In addition, although the disclosure may refer at times to a "switch" and "switching," for the purposes of this invention, the terms "switch" and "switching" may include both switching and routing. The network device in <FIG> is shown as network switch <NUM>. Network switch <NUM> is functionally connected to Central Processing Unit (CPU) <NUM> and other external devices <NUM>. External devices <NUM> may be other external processors, external memory, other network devices such as servers, routers, or computers, and/or other network switches to expand the switching capability. CPU <NUM> can be used to program network switch <NUM> based on desired rules or protocols for packet processing. Data received from network device(s) <NUM>, <NUM>, <NUM>, and <NUM> by ports <NUM> can be processed by network switch <NUM> independent of CPU <NUM> based on the programmed instructions. The processed data is then redistributed across the ports <NUM> to the appropriate network device(s) based on the programmed packet processing rules. The network switch shown in <FIG> can be an integrated, modular, single chip solution. In some embodiments, network switch <NUM> includes an application-specific integrated circuit (ASIC) constructed according to the packet processing rules, a field programmable gate array (FPGA), or any other type and form of dedicated silicon logic or processing circuitry capable of processing and switching packets. Additionally and/or alternatively, network switch <NUM> can be a plurality of individual components on a circuit board, or implemented on a general purpose device, or general purpose devices, through software.

Still referring to <FIG>, in forwarding a multicast packet the network switch <NUM> can receive the multicast packet from the network device(s) <NUM>, <NUM>, <NUM>, and <NUM> and process the packet. While the word "packet" is used, it should be understood that the disclosed process can work with other types of data including cells, frames, datagrams, bridge protocol data unit packets, packet data, etc. Packet processing can include reading, modifying, and classifying the packet, changing the packet forwarding behavior, removing and/or appending information to the packet, mirroring the packet to another port, storing the packet in a buffer, reordering the packet in a series of packets, sending the packet to a service queue, or changing the type of packet. For example, network switch <NUM> can replicate the packet and choose port <NUM> as the egress port, which can thereafter forward the packet to network switch <NUM>. The egress port and final network device destination are determined by data contained in the packet. In Layer <NUM> (L2) forwarding a packet is switched within a network to one or more egress ports of the network switch. In L3 forwarding a packet can be replicated and sent to multiple destinations on a single egress port or across multiple egress ports. In some embodiments, the final packet destination is a successive network device, and the packet is forwarded from network switch <NUM> through a series of network devices before the final destination is reached.

The packet contains information for replicating and forwarding the packet to the appropriate destinations on the network. A packet is originally received on a source port noted by network switch <NUM> and it can then be replicated and forwarded to the same or one or more other ports that belong to the multicast group indicated by the information contained in the packet. The multicast group can be indexed against a forwarding table (L2) or IP routing table (L3) to obtain a listing of destinations subscribed to the multicast group. In multicast, packets tagged as belonging to a multicast group are sent to subscribed destinations that have indicated to network switch <NUM> that they belong to the multicast group. The single packet can be replicated and forwarded to a plurality of destinations without flooding the network, such that only a single packet is transmitted to each destination.

The packet can be switched, bridged, or forwarded based on the destination MAC address contained in the packet. If the packet indicates that the VLAN ID of the packet is the same as the VLAN ID of the source, then it is forwarded according to Layer-<NUM> values of the packet. Intra-network switching based on MAC address information is called Layer <NUM> (L2) forwarding because it operates on the data link layer (OSI Layer <NUM>). In L2 forwarding, network switch <NUM> can use the multicast group number and reference a lookup table (i.e., a forwarding table) to obtain the list of destinations indexed for the multicast group. In some embodiments, the destination list may be a binary port bitmap vector of all ports in network switch <NUM> that are subscribed to that multicast group. Still in other embodiments, the list may be a binary port bitmap vector of all ports in network switch <NUM> with the value of each vector position indicating if the port is enabled or disabled. The port bitmap vector can be of any length, such as <NUM> bits in length. An example lookup table for indexing multicast group numbers (MCGNs) and port bitmap vectors is included below:
<IMG>.

In the port bitmap vector shown in Table <NUM>, each value in the vector represents a port; an enabled port can be marked by a "<NUM>" and a disabled port can be marked by a "<NUM>. " In some embodiments, the port bitmap vector lists only those ports that are a member of the multicast replication group. The packet is then replicated to each port in the vector. The port bitmap vector can also be a value represented in various other format. In some embodiments, the destinations list may include a list of MAC addresses for devices subscribed to the multicast group, and network switch <NUM> may then replicate the packet to the MAC address over the appropriate ports. The network switch <NUM> may reference a MAC address table to find the appropriate egress port corresponding to the destination MAC address. The MAC address table is built by network switch <NUM> using the source address of packets that are received. If the MAC address for the destination is not found, network switch <NUM> will flood the packet to all ports except the source port to ensure it reaches the appropriate destination. The destination then replies, and its MAC address is added to the table for future forwarding. If the MAC address of the destination is already known, network switch <NUM> sends the packet to the appropriate destination MAC address through the correct port determined from the MAC address table. It can also be built through various communication protocols designed to discover link layer addresses, such as Internet Group Management Protocol (IGMP) Snooping. The same information can be used to develop the port bitmap vector indexed according to multicast group number.

<FIG> is a flow chart illustrating process <NUM> for reducing bias in L2 multicast replication, according to one embodiment of the present invention. Process <NUM> can be performed by one or more network devices. For example, process <NUM> can be performed by network switch <NUM> and/or hardware contained within it, such as an ASIC chip. In step <NUM>, a data packet is received, and in step <NUM> the data packet is processed to retrieve a multicast group number. In step <NUM> the L2 destination list corresponding to the multicast group number is obtained. The destination list may, for example, be a port bitmap such as a bit vector, or listing of MAC addresses as described individually above. The L2 destination list may be circularized such that it has no end and each destination in the list is connected to two others to form a circle, with what would be the end value pointing back to the first value. For example the L2 destination list may be a circularized bit vector of n ports. The nth port points to the first port such that the bit vector is circularized, and no matter the starting port, proceeding sequentially through the circularized bit vector each port will be passed. The multicast group number may be indexed in a lookup table such as Table <NUM> and used to obtain the corresponding destination list, in Table <NUM> a port bitmap vector.

In step <NUM>, the process includes randomly selecting an initial destination within the L2 destination list. For example, the network switch may use a random number generator to select a port in the port bitmap vector as a starting point for forwarding the packet. This results in a randomized sequence of ports or destinations as compared to the initial port bitmap vector. While the term random is used, for the purposes of this invention random includes both random and pseudo-random. For example, the randomly selected initial destination may be a pseudo-randomly selected initial destination, the random number generator may be a pseudo-random number generator, and the randomized sequence may be a pseudo-randomized sequence. The process shown in step <NUM> uses the randomly selected initial destination to randomize the replication process, ensuring that from one packet to the next a port is not favored over another port such that a bias is introduced into the replication process. In step <NUM>, beginning at the initial destination, the packet is replicated according to the circularized L2 destination list. As described above, the circularized list ensures each destination in the list will receive a packet no matter the starting point. According to the exemplary embodiment shown in <FIG>, replication proceeds sequentially along the circularized L2 destination list, starting from the initial destination, to the end of the list, and then moving back to the beginning of the list until a packet has been replicated to each destination.

<FIG> is an example of packet handling in process <NUM> of <FIG>for multiple packets, according to an exemplary embodiment. The destination list from process <NUM> is shown as port bitmap vector <NUM>, which includes a listing of <NUM> ports, Port <NUM>-Port <NUM>. While shown to include <NUM> ports, the port bitmap vector may be of any length and/or size according to how many ports are a member of the multicast group. In the example shown in <FIG>, Port <NUM> is randomly selected as the starting point <NUM>, and packet <NUM> is replicated to each port in the vector, beginning at starting point <NUM> and ending at port <NUM>, or end point <NUM>. A random (i.e., random or pseudo-random) starting point <NUM> is selected for packet <NUM> at port <NUM>, and packet <NUM> is likewise replicated to each port in port bitmap vector <NUM>. The port bitmap vector is circularized such that at port <NUM>, because packet <NUM> has not been replicated to each port in the port bitmap vector, the replication process returns to port <NUM> and continues replicating packet <NUM> until it has been replicated to each destination port until the end point <NUM> at port <NUM>. Likewise, the randomly selected starting point <NUM> for packet <NUM> replication is at port <NUM>, and packet <NUM> is replicated from port <NUM> through port <NUM>, then back to port <NUM> and up to the end point <NUM> at port <NUM>, such that it is replicated to all ports in the vector. In another embodiment, the port bit map may include all ports of network switch <NUM> and indicate instead which ports are subscribed and which ports are not subscribed to the multicast group, and the packet will only be replicated to the subscribed ports. As shown in <FIG>, when the next packet in the multicast group is received, process <NUM> is repeated, and another starting point is randomly selected in the L2 destination list. The starting point may or may not be the same starting point as the last packet in the multicast group, and by introducing a random or pseudo-random starting point, process <NUM> minimizes the bias in the L2 multicast replication such that a favored port for a given data packet cannot be reasonably predicted.

For example, it may take one clock cycle to replicate a packet to each port. With a clock cycle of <NUM> ns, port <NUM> will receive packet <NUM><NUM> ns before port <NUM>. If the replication sequence always begins at port <NUM>, port <NUM> will have a persistent bias over port <NUM> such that it will always receive data <NUM> ns sooner. Referring back to <FIG> and <FIG>, randomly selecting a start point in step <NUM> distributes the bias packet-to-packet, such that it cannot be reasonably predicted which port will receive the packet first, effectively eliminating the bias.

<FIG> is a flow chart illustrating process <NUM> for reducing bias in L2 multicast replication, according to another embodiment of the present invention. Process <NUM> can be performed by one or more network devices. For example, process <NUM> can be performed by hardware in network switch <NUM>. Process <NUM> is shown to include step <NUM>, selecting a multicast group number and retrieving a corresponding L2 destination list. An example destination list is shown in <FIG> as a port bitmap vector. While port bitmap vector <NUM> is shown in sequential order, in some embodiments not all <NUM> ports of a network switch are included. In some embodiments, port bitmap vector <NUM> may include fewer ports if not all ports are subscribed to the multicast group. Referring back to <FIG>, step <NUM> includes splitting the L2 destination list into n number of replication groups. Hardware such as ASIC(s) inside of network switch <NUM> may perform the split in some embodiments. The destination list may be split into any number of groups. Each group can contain a unique subset of destinations included in the destination list, such that together the groups include all destinations in the L2 destination list. The groups may be of equal or dissimilar sizes. For example, referring now to <FIG>, each replication group <NUM>, <NUM>, and <NUM> contains <NUM> ports of a <NUM> port bitmap vector. Continuing the example, there would be a total <NUM> replications to ensure each destination is included.

Referring back to <FIG>, in step <NUM>, process <NUM> is shown receiving a packet belonging to the selected multicast group number. In some embodiments, step <NUM> may occur before step <NUM>, such that the multicast group number selected in step <NUM> is derived from the received packet. In step <NUM>, process <NUM> is shown randomly selecting one of the n replication groups corresponding to the multicast group number of the packet and replicating the packet to the destinations listed in the replication group at step <NUM>. At step <NUM>, if the packet has not been replicated to each replication group corresponding to the multicast group number, process <NUM> returns to step <NUM> and randomly selects another replication group from the remaining pool of replication groups. In multicast replication each destination receives one copy of the packet, so each group is selected once. If the packet has been replicated to each replication group, the replication process for the packet is finished at step <NUM>.

<FIG> is a flow chart of an example of process <NUM>, shown as process <NUM>. Process <NUM> can be performed by one or more network devices. For example, process <NUM> can be performed by hardware in network switch <NUM>. Step <NUM> in process <NUM> includes receiving an incoming data packet. Step <NUM> may be the same and/or similar to <NUM>. Unlike process <NUM>, process <NUM> is shown to include receiving the multicast packet first. In some embodiments process <NUM> is similar to process <NUM> and the packet is not received until after the splitting process.

At step <NUM> the incoming data packet is processed and its multicast group number is determined. The multicast group number is indexed in a lookup table such as Table <NUM> to retrieve the destination list, described in step <NUM> as the <NUM>-bit port bitmap. The multicast group number may be used to obtain the destination list in accordance with any other networking protocol for L2 switching. Once the port bitmap is retrieved, step <NUM> includes splitting the port bitmap into <NUM> replication groups composed of <NUM> ports each. While shown as <NUM> groups of <NUM>, the port bitmap may be split into any number and size of replication groups. The replication groups may be split and stored in hardware so that packet switching may still be accomplished at wire speed. As discussed above, in some embodiments the replication groups for a given multicast group may be split before a multicast packet is received belonging to the multicast group. In such an embodiment the replication groups need only be created once, and they may then be used for more than one packet in the multicast group.

Using a pseudo-random number generator, step <NUM> includes selecting one of the <NUM> replication groups corresponding to the packet multicast group number. In a manner similar to process <NUM>, randomly or pseudo-randomly selecting the order of replication groups introduces randomness in the L2 switching sequence and eliminates bias from one port to another. Once a replication group is selected, the packet is replicated to all enabled ports in the replication group at step <NUM>. In some embodiments, the packet is replicated to all ports in the replication group. At step <NUM>, process <NUM> checks if the packet has been replicated once to each replication group. If the answer is no, process <NUM> reverts to step <NUM> and a remaining group is again selected with a pseudo-random number generator. If the answer is yes, process <NUM> ends the replication sequence for the packet.

<FIG> is an example of packet switching in process <NUM>, according to the present invention. Packet <NUM> is shown being replicated to replication group <NUM>, shown as Layer <NUM> Replication Group <NUM>, starting at port <NUM> and ending at port <NUM>, before proceeding at <NUM> to replication group <NUM>, shown as Layer <NUM> Replication Group <NUM>, and being replicated starting at port <NUM> and proceeding to port <NUM>. The above continues until packet <NUM> has been replicated to each replication group.

<FIG> also shows packet processing for Packet <NUM> of the same multicast group. According to process <NUM> a replication group is randomly selected using a pseudo-random number generator. In the example shown in <FIG>, packet <NUM> is replicated first to replication group <NUM>, shown as Layer <NUM> Replication Group <NUM>, starting at port <NUM> through port <NUM>, and then at <NUM> another replication group is randomly selected, and Packet <NUM> is replicated on port <NUM> through port <NUM> of replication group <NUM>, shown as Layer <NUM> Replication Group <NUM>. The process continues until packet <NUM> has been replicated to each replication group.

In <FIG>, the packet is replicated in a replication group to each port sequentially. Therefore, randomly selecting the groups only minimizes inter-group bias, and intra-group bias may still exist. For example, referring back to replication group <NUM> in <FIG>, port <NUM> will always receive the packet before port <NUM>, no matter when the group is chosen. In some embodiments, the intra-group bias may be eliminated by periodically updating the groups, additionally and/or alternatively alternating their size and number. Referring now to <FIG>, an example of the packet switching process <NUM> with an additional step of randomization for eliminating intra-group bias is shown. In <FIG>, the packet replicated and/or forwarding process within a group is varied by randomly selecting a start position within a group. Using a pseudo-random or random number generator, a random initial destination is selected within replication group <NUM>, shown as Layer <NUM> Replication Group <NUM>. Starting at randomly selected initial destination <NUM>, packet <NUM> is replicated to port <NUM> through port <NUM>, then port <NUM> and port <NUM>, end point <NUM>. Like the destination list in process <NUM>, the port bitmap vector of <NUM> ports in replication group <NUM> is circularized such that no matter the initial starting point, each destination receives a packet. Using a pseudo-random number generator at <NUM>, another replication group corresponding to the multicast group of packet <NUM> is chosen, shown as replication group <NUM>. The pseudo-random number generator is also used to choose a random initial destination, shown as initial destination <NUM>. Packet <NUM> is then replicated in the same manner as it was replicated for replication group <NUM>. The process continues until packet <NUM> has been replicated to each replication group. Packet <NUM> is then processed by the network switch. Like packet <NUM>, a random replication group corresponding to the multicast group number is selected, shown as replication group <NUM>. Start point <NUM> is randomly selected within the group and packet <NUM> is replicated along the circularized vector until it has been replicated to each destination. Another group is randomly selected, shown as replication group <NUM>, and again, starting at random start point <NUM>, packet <NUM> is replicated along the circularized vector. The process continues until packet <NUM> has been replicated to each replication group. The process is the same for packet <NUM>.

<FIG> is another example of the packet switching process <NUM> with an additional step of randomization, according to another embodiment of the present invention. In <FIG>, the random/pseudo-random number generator is used to randomly reorder the sequence of the destination list before it is split in replication groups. Each replication group accordingly contains a random selection of destinations from the port bitmap. Process <NUM> then carries on as described above with reference to <FIG>, except that each group now contains a random assortment of destinations from the initial destination list.

The packet can also be switched, bridged, forwarded, and routed based on the destination IP address contained in the packet across networks in Layer <NUM> (L3) multicast switching. The network device <NUM> can perform the L3 multicast switching (i.e.,. switching and/or routing) in hardware. For example, the network device <NUM> can use an ASIC to perform L3 switching at line speed. Network switch <NUM> processes the packet and retrieves the multicast group number, which is used to obtain a destination list corresponding to the multicast group number. The destination list may be a linked list, including for example a series of next hops or a combination VLAN and port bitmap vector, etc..

L3 multicast uses a multicast routing protocol to establish the linked lists. The network switch <NUM> can use various multicast routing protocols including but not limited to Internet Group Management Protocol (IGMP), Protocol Independent Multicast-Sparse Mode (PIM-SM), Protocol Independent Multicast-Dense Mode (PIM-DM), etc. In L3 multicast a single packet may be routed across networks as needed. For instance, if a single egress port contains multiple destinations, the packet can be replicated as many times as necessary to send to all domains in the Virtual Local Area Network (VLAN) associated with the egress port, as well as replicated to all other destinations, including VLANs that subscribe to the multicast group.

<FIG> is a flow chart illustrating process <NUM> for reducing bias in L3 multicast replication, according to one embodiment of the present invention. Process <NUM> can be performed by one or more network devices. For example, process <NUM> can be performed by network switch <NUM> and/or hardware contained within it such as an ASIC chip. Process <NUM> can be performed additionally and/or alternatively with processes <NUM>, <NUM>, and/or <NUM> in order to reduce bias in both L2 and L3 switching for a multicast packet. Like processes <NUM>, <NUM>, and <NUM>, process <NUM> is fundamentally concerned with introducing randomness in multicast replication sequencing to eliminate the bias from one destination to another.

Process <NUM> is shown to include selecting a multicast group number in step <NUM>. In some embodiments, the multicast group number is determined by examining an incoming multicast packet. In other embodiments, the network switch periodically selects multicast group numbers for process <NUM>. Step <NUM> includes obtaining an L3 destination list corresponding to the multicast group. The L3 destination list may be a linked list or replication group, for example a linked list including a series of next hops. In some embodiments, the linked list additionally and/or alternatively contains a series of {VLAN, port bitmap} vectors representing destinations. The linked list may be obtained by indexing the multicast group number in a lookup table to obtain a replication group. The replication group may obtain a replication list (i.e., a linked list) containing a series of next hops and/or a port bitmap vector. The lookup tables may be L3 IP routing tables formed by routing protocols such as Internet Group Management Protocol (IGMP), Protocol Independent Multicast-Sparse Mode (PIM-SM), Protocol Independent Multicast-Dense Mode (PIM-DM), etc..

Process <NUM> is shown to include step <NUM> including creating m copies of the replication lists (i.e., linked lists), wherein each copy contains a random order of destinations. Using a random number generator, software contained in a network switch can randomly reorder the sequence of destinations in each copy of the destination lists. While the term randomly reorder is used, as discussed above for the purposes of this disclosure random includes random and pseudo-random, such that a randomly reordered sequence of destinations may be a randomly or only a pseudo-randomly reordered sequence of destinations. Any number of replication list copies may be created for example, <NUM>n, where n is configurable by software. Each replication list copy will have the same destinations but the order of the destinations will be randomized.

While process <NUM> is described above in relation to L3 multicast replication, it may also be applied to L2 replication. In L2 replication, each destination belongs to the same network, thus the {VLAN, port} linked list includes various destinations only across ports of a network switch. For successful L2 replication step <NUM> may therefore include randomizing the order of ports in the {VLAN, port} linked list to obtain m copies of the linked list per multicast group, each with a difference sequence of ports in the list but the same VLAN value corresponding to the L2 domain.

When a multicast packet in the multicast group is received as in step <NUM>, one of the <NUM>n replication list copies corresponding to that multicast group is randomly selected in step <NUM>. Step <NUM> includes replicating the packet to all destinations in the replication list. Steps <NUM>-<NUM> can take place in hardware in a network switch such that replication can occur at wire speed. The process will repeat for each individual packet in a multicast group, so the packets will be replicated to next hops in different orders. This reduces short term bias in the L3 replication sequence.

<FIG> is a flow chart illustrating process <NUM> according to a specific embodiment. Process <NUM> can be performed by one or more network devices. For example, process <NUM> can be performed by network switch <NUM> and/or hardware contained within it such as an ASIC chip. Process <NUM> can be similar and/or identical to process <NUM>. Step <NUM> includes receiving an incoming data packet, and step <NUM> includes determining the multicast group the data packet belongs to. In some embodiments, step <NUM> is performed later, and the multicast group is selected from a list of multicast groups, for example, as shown in process <NUM>. After the multicast group is determining, step <NUM> includes obtaining the multicast replication list indexed by multicast replication group number. Using the replication list, step <NUM> includes generating <NUM> copies of the replication list, each with a randomly ordered sequence of next hops. While shown as <NUM> copies, any number of replication list copies may be created. As discussed above, the replication lists may include next hops and/or port bitmaps belonging to the multicast group number. Using a pseudo-random number generator, step <NUM> includes randomly selecting one of the <NUM> replication list copies corresponding to the multicast group number, and step <NUM> includes replicating the packet to each next hop in the replication list.

<FIG> is an example of packet processing for processes <NUM> and <NUM> after the replication lists have been copied, according to an exemplary embodiment. Packet <NUM> is shown being replicated according to the order of destinations in replication list <NUM>, shown as Layer <NUM> Replication List <NUM>. Replication list <NUM> is shown to include <NUM> next hops, though it should be understood that the replication lists may be of any length, so long as each list copy has the same destinations as the others. As shown, the order of next hops in replication list <NUM> is random. For every packet in the multicast group, another replication list is randomly selected. For example, packet <NUM> is shown being replicated according to replication list <NUM>, shown as Layer <NUM> Replication List <NUM>, and packet <NUM> is shown being replicated according to replication list <NUM>, shown as Layer <NUM> Replication List <NUM>. Because different packets in the same multicast group are replicated according to randomly selected replication lists corresponding to the replication group, the short-term bias in L3 replication is reduced.

In some embodiments, further steps can be taken to reduce long-term bias in L3 packet switching. Long-term bias results from the fact that the replication list copies are static. For example, after the replication list copies are created and the order of destinations in each is randomly reordered, it is possible that next hop <NUM> is always before next hop <NUM>. Because the lists are static, no matter which list is chosen next hop <NUM> will have a bias as compared to next hop <NUM>. Referring now to <FIG>, an update process <NUM> is shown that can be performed in addition to processes <NUM> and <NUM> to reduce long term bias in L3 replication, according to an exemplary embodiment. Process <NUM> can be performed by one or more network devices. For example, process <NUM> can be performed by network switch <NUM> and/or hardware contained within it such as an ASIC chip. In process <NUM>, a multicast group number is selected by the network switch in step <NUM>, and one of n pre-existing replication list copies corresponding to the multicast group is retrieved in step <NUM>. In some embodiments, the replication list is randomly selected using a pseudo-random number generator. In some embodiments, the replication list is selected according to a schedule. For example, software within a network switch may be configured to sequentially select replication list copies to ensure that each is periodically updated. Step <NUM> includes randomly reordering the sequence of destinations in the replication list. In some embodiments, step <NUM> is similar to step <NUM> of process <NUM>, in that the order of the destinations in the copies are randomly ordered. Process <NUM> may be periodically initiated within a network switch to eliminate long-term bias. In some embodiments, process <NUM> is triggered by a multicast packet arriving for the selected multicast group. In some embodiments, multicast groups are updated according to process <NUM> randomly.

<FIG> is a detailed block diagram of a network switch <NUM> shown in <FIG>, according to the present invention. The network switch <NUM> is shown to include CPU Management Input Controller (CMIC) <NUM>. In some embodiments, CMIC <NUM> includes <NUM> PCIe ports. CMIC <NUM> allows network switch <NUM> to connect to CPU <NUM> which can be used to access network switch <NUM> and program processor <NUM>. Processor <NUM> can be used to program and control the network switch <NUM> including L2/L3 processing <NUM>. Processor <NUM> is any logic circuitry that responds to and processes instructions fetched from the memory. In some embodiments, processor <NUM> is an application-specific integrated circuit (ASIC). Processor <NUM> enables wire or line speed communication between its various internal modules and ports <NUM>. Processor <NUM> may also be a field programmable gate array (FPGA) or any other type and form of dedicated silicon logic or processing circuitry.

L2/L3 Processing <NUM> is connected to ports <NUM> by ingress pipeline <NUM> and egress pipeline <NUM>. Ports <NUM> may be fast Ethernet ports, gigabit Ethernet ports, management ports, Direct Attach Copper (DAC) ports, and/or PCIe ports or other common ports depending on the application. For example, ports <NUM> may include <NUM> gigabit Ethernet ports. It should be noted that any number of ports can be provided and additional interconnects for external devices <NUM> may be provided as necessary. Ports <NUM> can receive a packet at a network switch <NUM> from network device(s) <NUM>, <NUM>, <NUM>, and/or <NUM> and pass the packet to processor <NUM>. The packet can be passed by ingress pipeline <NUM> to L2/L3 processing <NUM> for replication and forwarding. Ingress pipeline <NUM> may include parsers and other tiles for packet processing. The packet is passed to L2/L3 processing <NUM> which passes the processed and/or replicated packets to egress pipeline <NUM> to finally forward the packets through ports <NUM> to the appropriate network device(s) <NUM>, <NUM>, <NUM>, and <NUM>. The present invention can accommodate various types of data, and "packet" can include packet, cell, frame, datagram, bridge protocol data unit packet, packet data, etc..

<FIG> illustrates that L2/L3 Processing <NUM> includes random number generator <NUM> and forwarding tables <NUM>. Random number generator <NUM> may be any type of random number generator that can produce random or pseudo-random numbers including non-deterministic random number generators and deterministic or pseudo-random number generators. Random number generator <NUM> may be implemented in software or included as a hardware component. Forwarding tables <NUM> may include L2 destination lists indexed to multicast group numbers, such as L2 MAC address tables for L2 switching. L2 switching forwards packets intra-network. Forwarding tables <NUM> may also include L3 IP routing tables for L3 switching or routing, which forwards packets inter-network and may include linked lists. Packet forwarding and processing using random number generator <NUM> and forwarding tables <NUM> is explained in detail above. Forwarding tables <NUM> may contain destination lists and/or replication lists, such as the port bitmap vectors for L2 switching and the linked lists for L3 switching.

Network switch <NUM> may also include other components not shown. For example network switch <NUM> may include Ethernet port interface controllers, gigabit port interface controllers, internet port interface controllers, a buffer, and a memory management unit.

The construction and arrangement of the systems and methods as shown in the various exemplary embodiments are illustrative only. Although only a few embodiments have been described in detail in this disclosure, many modifications are possible (e.g., variations in port or destination quantity, data types, methods of randomization or pseudo-randomization, values of parameters, arrangements, etc.). For example, the position of elements may be reversed or otherwise varied, the connections between elements may be direct or indirect, such that there may be one or more intermediate elements connected in between, and the nature or number of discrete elements or positions may be altered or varied. Accordingly, all such modifications are intended to be included within the scope of the present disclosure as long as they do not depart from the scope of the invention as it is depicted by the appended claims. The order or sequence of any process or method steps may be varied or re-sequenced according to alternative embodiments. Other substitutions, modifications, changes, and omissions may be made in the design, operating conditions, and arrangement of the exemplary embodiments as long as they do not depart from the scope of the invention as it is depicted by the appended claims. For example, the embodiments of the present disclosure may be implemented by a single device and/or system or implemented by a combination of separate devices and/or systems.

The present disclosure contemplates methods, systems, and program products on any machine-readable media for accomplishing various operations. The embodiments of the present disclosure may be implemented using existing computer processors, or by a special purpose computer processor for an appropriate system, incorporated for this or another purpose, or by a hardwired system. Embodiments within the scope of the present disclosure include program products comprising machine-readable media for carrying or having machine-executable instructions or data structures stored thereon. Such machine-readable media can be any available media that can be accessed by a general purpose or special purpose computer or other machine with a processor. By way of example, such machine-readable media can comprise RAM, ROM, EPROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to carry or store desired program code in the form of machine-executable instructions or data structures and which can be accessed by a general purpose or special purpose computer (i.e., ASICs or FPGAs) or any other machine with a processor. Combinations of the above are also included within the scope of machine-readable media. Machine-executable instructions include, for example, instructions and data which cause a general purpose computer, special purpose computer, or special purpose processing machines to perform a certain function or group of functions.

Claim 1:
A method of reducing bias in multicast replication, the method comprising:
receiving (<NUM>) a packet (packet <NUM>, packet <NUM>, packet <NUM>) at a network device (<NUM>);
determining (<NUM>) a multicast group from the packet;
obtaining (<NUM>) at least two or more destinations corresponding to the multicast group;
replicating the packet for the at least two or more destinations; and
forwarding the replicated packet to the at least two or more destinations in a randomized sequence,
wherein the at least two or more destinations are one or more egress ports of the network device,
wherein obtaining the at least two or more destinations comprises indexing a multicast group number that identifies the multicast group into a lookup table to obtain a port bitmap that corresponds to the multicast group, wherein the port bitmap is a listing of ports of the network device belonging to the multicast group, and
wherein forwarding the replicated packet to the at least two or more destinations in a randomized sequence comprises:
randomly (<NUM>) selecting an initial destination in the port bitmap, wherein the port bitmap is a circularized bit vector; and
forwarding (<NUM>) the replicated packet to according to the port bitmap, starting at the initial destination until the replicated packet has been forwarded to each port in the port bitmap.