PACKET FORWARDING APPARATUS AND METHOD USING FLOW SUBGROUP BASED PATH SELECTION FOR DYNAMIC LOAD BALANCING

• US 20150163146A1
• Filed: 09/17/2014
• Published: 06/11/2015
• Est. Priority Date: 12/05/2013
• Status: Active Grant

• Current Assignee: MediaTek Singapore Pte. Ltd. (MediaTek, Inc.)
• Original Assignee: MediaTek Singapore Pte. Ltd. (MediaTek, Inc.)
• Inventors: Zhang, Ming, Chang, Jonathan
• Granted Patent: US 9,467,384 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

A packet forwarding apparatus has a path selection device used to generate a path selection signal for selecting a destination path from egress paths of an egress path group. The path selection device has a flow group based path selection circuit and a flow subgroup based path selection circuit. The flow group based path selection circuit sets the path selection signal based on a flow group into which a packet is categorized when a dynamic load balancing function is not applied to forwarding of the packet. The flow subgroup based path selection circuit sets the path selection signal based on a flow subgroup into which the packet is categorized when the dynamic load balancing function is applied to forwarding of the packet. Flows associated with the egress path group are categorized into flow subgroups, the flow subgroups are categorized into flow groups, and each flow includes packets with same tuple(s).

Claims

1. A packet forwarding apparatus, comprising:

a path selection device, configured to generate a path selection signal referenced for selecting a destination path from a plurality of egress paths belonging to an egress path group, the path selection device comprising;

a flow group based path selection circuit, configured to set the path selection signal based on a flow group into which a packet to be forwarded is categorized when a dynamic load balancing function is not applied to forwarding of the packet; and

a flow subgroup based path selection circuit, configured to set the path selection signal based on a flow subgroup into which the packet to be forwarded is categorized when the dynamic load balancing function is applied to forwarding of the packet;

wherein flows associated with the egress path group are categorized into a plurality of flow subgroups, the flow subgroups are categorized into a plurality of flow groups, and each of the flows includes a group of packets with same tuple(s).

2. The packet forwarding apparatus of claim 1, wherein the flow subgroup based path selection circuit is further configured to determine whether to perform the dynamic load balancing function for the packet according to the flow subgroup of the flow group.

3. The packet forwarding apparatus of claim 1, wherein the flow subgroup based path selection circuit comprises:

a flow rebalance table, having at least one entry configured to store a mapping between one flow subgroup of one flow group associated with one egress path group and one setting of the path selection signal; and

the flow subgroup based path selection circuit is configured to set the path selection signal for the packet to be forwarded when the flow rebalance table contains an entry corresponding to the flow subgroup of the flow group associated with the egress path group.

4. The packet forwarding apparatus of claim 3, further comprising:

a path rate monitor, comprising;

a plurality of monitoring circuits, configured to monitor data rates of the egress paths to generate path rate monitor values, respectively;

wherein the flow rebalance table is updated based at least partly on the path rate monitor values.

5. The packet forwarding apparatus of claim 4, wherein each of the monitoring circuits comprises:

a first counter, configured to count a number of bytes transmitted through a corresponding egress path during a predetermined period, and accordingly generate an instantaneous path rate value;

a second counter, configured to generate a weighted average of an average path rate value and the instantaneous path rate value to update the average path rate value which acts as a path rate monitor value of the monitoring circuit.

6. The packet forwarding apparatus of claim 4, wherein the path rate monitor further comprises:

a comparing circuit, configured to compare each of the path rate monitor values with a predetermined threshold value, and generate an indication signal when any of the path rate monitor values exceeds the predetermined threshold value; and

the packet forwarding apparatus further comprises;

a controller, configured to update the flow rebalance table when notified by the indication signal.

7. The packet forwarding apparatus of claim 4, further comprising:

a heavy flow monitor, configured to capture at least one heavy flow subgroup from the flow subgroups of the flow groups associated with the egress path group, wherein traffic of the at least one heavy flow subgroup is higher than traffic of other flow subgroups of the flow groups;

wherein the controller is configured to update the flow rebalance table according to the path rate monitor values generated by the path rate monitor and the at least one heavy flow subgroup captured by the heavy flow monitor.

8. The packet forwarding apparatus of claim 7, wherein the controller is further configured to update the flow rebalance table having an entry corresponding to a specific heavy flow subgroup of a specific flow group when the specific heavy flow subgroup of the specific flow group is evicted from the at least one heavy flow subgroup.

9. The packet forwarding apparatus of claim 2, further comprising:

a controller, configured to update the flow rebalance table having an entry corresponding to a specific egress path of the egress path group when the specific egress path is removed from the egress path group.

10. The packet forwarding apparatus of claim 1, wherein the egress path group is one of an equal-cost multi-path (ECMP) group and a link aggregation group (LAG).

11. A packet forwarding method, comprising:

generating a path selection signal referenced for selecting a destination path from a plurality of egress paths belonging to an egress path group, wherein the generating a path selection signal comprises;

when a dynamic load balancing function is not applied to forwarding of a packet, performing a flow group based path selection to set the path selection signal based on a flow group into which the packet to be forwarded is categorized; and

when the dynamic load balancing function is applied to forwarding of the packet, performing a flow subgroup based path selection to set the path selection signal based on a flow subgroup into which the packet to be forwarded is categorized;

wherein flows associated with the egress path group are categorized into a plurality of flow subgroups, the flow subgroups are categorized into a plurality of flow groups, and each of the flows includes a group of packets with same tuple(s).

12. The packet forwarding method of claim 11, wherein the flow subgroup based path selection further determines whether to perform the dynamic load balancing function for the packet according to the flow subgroup of the flow group.

13. The packet forwarding method of claim 11, further comprising:

setting a flow rebalance table having at least one entry configured to store a mapping between one flow subgroup of one flow group associated with one egress path group and one setting of the path selection signal;

wherein the flow subgroup based path selection sets the path selection signal for the packet to be forwarded when the flow rebalance table contains an entry corresponding to the flow subgroup of the flow group associated with the egress path group.

14. The packet forwarding method of claim 13, further comprising:

monitoring data rates of the egress paths to generate path rate monitor values, respectively; and

updating the flow rebalance table based at least partly on the path rate monitor values.

15. The packet forwarding method of claim 14, wherein the step of monitoring the data rates of the egress paths comprises:

concerning each of the egress paths,

counting a number of bytes transmitted through a corresponding egress path during a predetermined period, and accordingly generate an instantaneous path rate value; and

generating a weighted average of an average path rate value and the instantaneous path rate value to update the average path rate value which acts as a path rate monitor value of the egress path.

16. The packet forwarding method of claim 14, wherein the step of monitoring the data rates of the egress paths further comprises:

comparing each of the path rate monitor values with a predetermined threshold value; and

generating an indication signal when any of the path rate monitor values exceeds the predetermined threshold value; and

the packet forwarding method further comprises;

updating the flow rebalance table in response to the indication signal.

17. The packet forwarding method of claim 14, further comprising:

capturing at least one heavy flow subgroup from the flow subgroups of the flow groups associated with the egress path group,

wherein traffic of the at least one heavy flow subgroup is higher than traffic of other flow subgroups of the flow groups;

wherein the step of updating the flow rebalance table comprises;

updating the flow rebalance table according to the path rate monitor values and the at least one heavy flow subgroup.

18. The packet forwarding method of claim 17, further comprising:

updating the flow rebalance table having an entry corresponding to a specific heavy flow subgroup of a specific flow group when the specific heavy flow subgroup of the specific flow group is evicted from the at least one heavy flow subgroup.

19. The packet forwarding method of claim 12, further comprising:

updating the flow rebalance table having an entry corresponding to a specific egress path of the egress path group when the specific egress path is removed from the egress path group.

20. The packet forwarding method of claim 11, wherein the egress path group is one of an equal-cost multi-path (ECMP) group and a link aggregation group (LAG).