Load-aware ECMP with flow tables

A semiconductor chip for implementing load-aware equal-cost multipath routing includes a number of ports and several pipes, each pipe being coupled to a portion of ports on the semiconductor chip, and a central unit consisting of a state machine and multiple databases. The databases contain information regarding a communication network including an overlay network and an underlay network, and the state machine is implemented in hardware and can determine at least one feature of the overlay network and a corresponding group of paths within the underlay network.

TECHNICAL FIELD

The present description relates generally to Ethernet communication and, in particular, to load-aware, equal-cost multipath (ECMP) routing implementation with flow tables.

BACKGROUND

Equal-cost multipath (ECMP) routing is a routing strategy where packet forwarding to a single destination can occur over multiple best paths with equal routing priority. Multipath routing can be used in conjunction with most routing protocols because it is a per-hop decision made independently at each router. It can substantially increase bandwidth by load-balancing traffic over multiple paths; however, there may be significant limitation in deploying it in practice. For example, the ECMP route selection is essentially fixed to a flow-hash % ECMP-group-size, which returns the same result on different network nodes. The hash algorithms are usually not perfect; for instance, there can be biases and the distribution can be nonuniform. The more important problem with ECMP is that the concept of checking for instantaneous loading or congestion, while selecting a path, does not exist. Paths are fixed based on the flow-hash and statistically preprogrammed. Even when one tries to program desired paths by software (S/W), there is a severe limitation of response time and there is no mechanism for the reordering of packets, which renders it practically useless.

DETAILED DESCRIPTION

The subject technology is directed to methods and systems for load-aware equal-cost multipath (ECMP) routing implementation with flow tables. The disclosed ECMP technique helps with improving network performance factors such as lowering network congestion and latencies that are effective in minimizing packet loss. In the existing solutions, the ECMP groups and corresponding members are programmed statically, and there is no consideration of dynamic network situations such as instantaneous loading/congestion on ports or corresponding queues and the up/down state of ports and/or links indicated by the next-hop index. If the output ports are found to be down in a given router, then protection-switching logic provides preprogrammed alternatives, secondary and (if secondary is also down, then) tertiary choices, without any knowledge of dynamic congestion/loading on those alternative ports. The entire table structure may require reprogramming to address ports that went down, which might require a significant amount of time for detection and then correction by software (S/W).

The load-aware ECMP technique of the subject technology makes the entire ECMP infrastructure dynamically load balanced, with comparatively very small chip area and/or power cost. The load-aware ECMP also helps to reduce congestion in the networks and significantly reduce the tail latencies. Biases, weights and/or vectors can help take into account parameters affecting further hops in the underlay and overlay networks for desired path selection, which can dramatically improve the network performance. An overlay network (overlay) is a virtual network that is built on top of an underlying network infrastructure and/or network layer (the underlay network or underlay). The existing solution needs to update the entire undelay and overlay programming in response to a dynamic network situation, which is very time consuming and disruptive to the entire network. The same desired selection is also applied to secondary and tertiary protection-switching logic alternatives to avoid congestion on those links in case of down ports, avoiding network bottlenecks.

In the load-aware ECMP technique of the subject technology, the lowest amount of information is replicated per pipe (e.g., a data-communication pipe between two nodes), as there is no need to have bias/weight/vector programming inside the pipes, and also no need of port/queue quality metrics in every pipe. All programming and port/queue quality metrics are performed by the central module (only one copy for the entire chip), saving significant area, power and cost for chips with higher bandwidth, and hence more pipes. The load-aware ECMP solution has a fraction of the area, power, latency and cost of any other per pipe dynamic load-balancing solutions. This is because the path selection is not done locally per packet in the pipes, but centrally by a single state machine for all the pipes; an expensive time-stamp mechanism is not required to avoid reordering; it supports dynamic desired selection for overlay as well, based on corresponding biases/weights/vectors, without any packet reordering; it supports not only per-port, but per-port per-queue, quality metrics, which improves selection granularity to lowest possible; and it dramatically improves accuracy of the selection of desired port/queue and significantly expands the scope of applications for this load balancing. The disclosed central state machine is implemented in hardware, which is significantly faster and more favorable, compared to traditional implementation in S/W, for any exceptions handling, updates for down ports/links, and protection switching.

FIG.1is a block diagram illustrating an example of an abstract view for a pipe100of a load-aware ECMP, according to various aspects of the subject technology. The abstract view shows the pipe100of the load-aware ECMP routing including a level 1, overlay network110; a level 2, underlay network120; a protection-switching logic130; and a central module (also referred to as a central unit)140. The overlay network110includes an ECMP group table112, an ECMP member table114and a flow table116. The underlay network120includes an ECMP group table122, an ECMP member table124and a flow table126. The ECMP group table112receives a level 1 group-index102from forwarding lookup of a packet or from an access control list and generates group properties103. The group in the context of the present disclosure is a collection of paths with given characteristics. For example, from a source location (e.g., San Jose) to a destination (e.g., New York) there may be a number of (e.g.,10) paths. The group properties103is passed to an ECMP member of the ECMP member table114. The index of the ECMP member is given by a group base value (group_base) provided by the ECMP group table112+a group size as a hash value calculated based on packet characteristics (hash % group_size). The ECMP group table122receives an overlay next-hop104from the ECMP member tables114and generates group properties105. The group properties105is forwarded to an ECMP member of the ECMP member table124. The index of the ECMP member is given by group_base+hash % group_size. The output of the ECMP member table124is passed through a protection-switching logic130for the underlay next hop (NH) to reach an NH table to derive outgoing properties of the packet. The NH refers to the closet router/switch in the network that a packet can go through.

The central module140is coupled to all pipes on a given chip and implements many important features of the subject technology. The central module140remedies the shortcomings of the existing ECMP solutions discussed above. The central module140includes databases for level 1 (overlay) and level 2 (underlay) group tables (e.g., ECMP group tables112and124) and corresponding members (e.g., ECMP member tables114and124), NH to ports mapping, overlay NH's to underlay groups mapping, and dynamic port status. In the central module140there are also databases for any biases, weights and/or vectors for paths beyond the current hop and thresholds, as well as instantaneous loading and congestion information for port and queues per port. The state machine in the central module140goes entry-by-entry of level 1 group and/or member and level 2 group, and processes the loading, bias and port status info to pick a desired NH and/or group per entry to be populated in the level 1 and/or level 2 member table. The desired NH and/or group at any level is the one that has less loading compared to other NH's and/or groups. Because the state machine has complete information about the device ports per NH, loading and/or congestion on each of those ports, as well as information about the faraway ports (on different devices) through the biases, it can determine which are the least loaded NH and/or group. The central module140provides periodic updates142to the overlay network110and the underlay network120. When the hit bit corresponding to an index is 1, it is set to 0 and the member table does not get updated. When the hit bit is 0, the member table is updated with desired NH and/or group. The programmed inactivity periods of the central module140decide the update frequency.

The flow tables116and126are provided by the subject technology for finer-grained control, in conjunction with the controls described above. The level 1 and level 2 group tables (e.g., ECMP group tables112and124) can be enabled to use the flow tables116and126, respectively. The flow tables116and126can record the flow using the hash calculated on the flow variables (e.g., 5 tuple) and corresponding chosen desired link at the same time of populating the new flow table. The flow tables116and126can record any number of flows per group and are only limited by the flow table scales. The flows do not change the desired selection, unless minimum inactivity periods on the earlier selection are reached, using the same hit bit mechanism described herein. This will avoid packet reordering and disruptions to the network. Configurable overrides for this behavior are also provided. If the flows remain inactive for the programmed time period (no packets received for the flow, for that time period), the flows will be aged out (deleted from the flow table) to reduce the flow table scale requirements.

FIG.2is a block diagram illustrating an example of dynamically evaluated mapping200for desired paths of a load-aware ECMP, according to various aspects of the subject technology. In the dynamically evaluated mapping200, a first host A is connected to a first router R1, which in turn is connected through paths (links) P5, P7, P15and P19to routers R2and R3of an underlay ECMP group210and routers R4and R5of an underlay ECMP group212. The routers R2and R3are connected through paths P1and P9to a router R6of an overlay ECMP group214, and the routers R4and R5are connected through paths P21and P2to a router R7of the overlay ECMP group214. The routers R6and R7are connected via paths P25and P22to a second host B.

Routers have info on port and/or queue loading on their own ports only. The quality of links beyond the current hops need to be programmed as biases/weights/vectors in group tables. For example, when the links (paths) P9and P22are facing congestion instantaneously, for example, due to bandwidth limitation, the router R1may or may not see the resultant loading and/or congestion on its port P7and corresponding queues, however the bias against the R3-to-R6link (P9) needs to be programmed in an underlay group table (e.g.,122ofFIG.1) and also bias against R7-to-B (P22) has to be programmed in an overlay group table (e.g.,112ofFIG.1). To take care of this situation, the central state machine of the central module140ofFIG.1can pick R6for overlay and R2for underlay as being desired at the time. When eventually R7-to-B link (P22) clears up, the state machine picks R7as overlay as a desired choice at that time. However, the hit bit mechanism will make sure updates to pipe tables will wait for a programmed minimum inactivity period on an earlier selection. This, in turn, makes sure that all the packets sent on that path in the given pipe and given flow are always ahead of the packets to be sent on the new updated path, avoiding the undesired reordering of the packets.

To make sure there is no packet reordering when the desired port selection changes for a given packet-flow, there exists a programmable minimum inactivity period before the change is actually updated into member tables in the pipes. The central state machine sets the hit bit corresponding to an entry of 0, and if there was no packet hitting the entry, then the hit bit is set to 1 when the state machine returns to read it again after the specific period. The minimum inactivity period is to let all the previous packets, from the same flow and using the previous path always, be ahead of the packets that will see the updated path. The minimum inactivity for a given member entry is enforced as follows. There is a hit bit maintained per entry of the level 2 member table that is set to 1 when the entry is referenced by a packet. This bit is checked at the time of periodic state machine updates to the member table. If the checked hit bit is 1, it is set to 0 and no update is made to the entry. If the hit bit is 0, the update is made to the entry. If the update rate of the state machine per entry is corresponding to the programmed minimum activity period, that period will automatically be enforced for a minimum inactivity check.

FIGS.3A and3Bare block diagrams illustrating examples of static ECMP mapping in a pipe300A and load-aware dynamic ECMP mapping in a pipe300B, according to various aspects of the subject technology. The static ECMP mapping is performed in pipe databases of the pipe300A to be read by packets. As shown inFIG.3A, the ECMP group table310provides group base and size information302to the ECMP members table320. The size information302identifies a group base322and a group size of 4, which includes NHs NH1, NH2, NH3and NH4. In the pipe300A, all the applicable members are preprogrammed. In the protection switching logic330, secondary NH is picked randomly from the group using a flow-hash, and the tertiary NH is statically selected from the group.

The dynamic ECMP mapping of the subject technology is performed in pipe databases of the pipe300B to be read by packets. As shown inFIG.3B, the ECMP group table310similarly provides group base and size information302to the ECMP members and hit bit table340. The size information302identifies a group base342and a group size of 4. The desired selection can be expanded to the lowest granularity of per-queue-per-port. In the example of two queues per port, the group base342includes a first desired selection (NH2, NH1, NH2and NH1) and second desired selection (NH5, NH1, NH2and NH8) per entry. The central state machine considers the instantaneous loading on the ports and/or queues corresponding to NH, any biases/weights/vectors programmed for accounting into parameters beyond this hop, before selecting the desired NH per entry as well as secondary and tertiary NH. The protection switching logic350can select the desired secondary and tertiary NH. The first desired selection is for incoming packets having a class of service 0 and the second desired selection is for incoming packets having a class of service 1.

FIG.4is a schematic diagram illustrating an example of a per-chip view400for load-aware ECMP, in accordance with some aspects of the subject technology. The per-chip view400shows four pipes including pipe410(pipe 1), pipe420(pipe 2), pipe430(pipe 0) and pipe440(pipe 3). Each of the pipes410,420,430and440are connected to one quarter of the ports on the chip. A central ECMP database and state machine450receives ports status and loading information452and is in communication with the pipes410,420,430and440to provide periodic updates to the ECMP members (e.g.,114ofFIG.1) of the pipes410,420,430and440, as discussed above with respect toFIG.1. The load-aware desired paths of the subject disclosure are set up by the state machine450in advance, instead of packets choosing the paths one by one. Further, the disclosed scheme takes care of minimum programmed inactivity periods on a given path before updating it to the new one, to avoid undesired reordering of packets. These features are among the differentiating aspects of the subject technology that enable a centralized and aggregated implementation (without any further cost) for the entire chip. These differentiating aspects also support other advantageous feature described above, for example, using a fraction of the area, power, latency and cost of any other per pipe dynamic load-balancing solutions, or being faster and more favorable compared to the traditional S/W implementations due to the use of the state machine450.

FIG.5is a flow diagram illustrating an example of a S/W process500, in accordance with some aspects of the subject technology. The S/W process500starts at operation block502, where the S/W programs underlay and/or overlay group tables (e.g.,122and112ofFIG.1) and members per group (e.g.,124and114ofFIG.1) in the pipe database. At operation block504, the S/W programs underlay and/or overlay group tables and members per group, port-to-NH mapping, biases, weights and/or vectors for the group and thresholds in the central module databases. At operation block506, the S/W continues updating biases, weights and/or vectors for the paths in the central module (e.g.,140ofFIG.1). At this point, the control of the S/W process500is passed to the operation block502for the process to continue.

FIG.6is a flow diagram illustrating an example of a central module process600, in accordance with some aspects of the subject technology. The central module process600starts at operation block602, where the central module receives live updates and process to calculate quality metrics. At operation block604, the central module goes entry by entry in level 1 group1, and at control operation block606, the central module checks whether overlay NH and the corresponding underlay group are still favorable. If the answer is yes, at control operation block608, the central module continues to check whether the underlay NH and secondary and tertiary selections are still favorable. If the answer to the checking in the control operation block606is no, at operation block612the desired selection is changed, and control is passed to operation block610. If at the at control operation block608, the underlay NH and secondary and tertiary selections are favorable, the control is passed to operation block610, where an atomic update to all pipes is initiated.

FIG.7is a flow diagram illustrating an example of a pipe process700, in accordance with some aspects of the subject technology. The pipe process starts at operation block702, where the pipe processor performs group and member look ups and derives destinations, as is normally done in ECMP. At operation block704, the pipe processor sets hit bit corresponding to the reference entries, and at operation block706, selects secondary and tertiary options in case of a port outage. At control operation block708, the pipe processor checks the corresponding hit bit when updating from the central state machine. If the hit bit is equal to zero, at operation block710the update from the central state machine is accepted and the control is passed to operation block702. If the hit bit is equal to 1, at operation block712, the update from the central state machine is ignored and the control is passed to operation block702.

FIG.8is an electronic system800within which some aspects of the subject technology are implemented. The electronic system800can be, and/or can be a part of, the network switch of a data center or an enterprise network. The electronic system800may include various types of computer readable media and interfaces for various other types of computer readable media. The electronic system800includes a bus808, one or more processing unit(s)812, a system memory804(and/or buffer), a ROM810, a permanent storage device802, an input device interface814, an output device interface806, and one or more network interfaces816, or subsets and variations thereof.

The bus808collectively represents all system, peripheral, and chipset buses that communicatively connect the numerous internal devices of the electronic system800. In one or more implementations, the bus808communicatively connects the one or more processing unit(s)812with the ROM810, the system memory804, and the permanent storage device802. From these various memory units, the one or more processing unit(s)812retrieves instructions to execute and data to process in order to execute the processes of the subject disclosure. The one or more processing unit(s)812can be a single processor or a multi-core processor in different implementations. In one or more aspects, the one or more processing unit(s)812may be used to implement the processes ofFIGS.5,6and/or7.

The ROM810stores static data and instructions that are needed by the one or more processing unit(s)812and other modules of the electronic system800. The permanent storage device802, on the other hand, may be a read-and-write memory device. The permanent storage device802may be a non-volatile memory unit that stores instructions and data even when the electronic system800is off. In one or more implementations, a mass-storage device (such as a magnetic or optical disk and its corresponding disk drive) may be used as the permanent storage device802.

In one or more implementations, a removable storage device (such as a floppy disk, flash drive, and its corresponding disk drive) may be used as the permanent storage device802. Like the permanent storage device802, the system memory804may be a read-and-write memory device. However, unlike the permanent storage device802, the system memory804may be a volatile read-and-write memory, such as random-access memory (RAM). The system memory804may store any of the instructions and data that one or more processing unit(s)812may need at runtime. In one or more implementations, the processes of the subject disclosure are stored in the system memory804, the permanent storage device802, and/or the ROM810. From these various memory units, the one or more processing unit(s)812retrieves instructions to execute and data to process in order to execute the processes of one or more implementations.

The bus808also connects to the input and output device interfaces814and806. The input device interface814enables a user to communicate information and select commands to the electronic system800. Input devices that may be used with the input device interface814may include, for example, alphanumeric keyboards and pointing devices (also called “cursor control devices”). The output device interface806may enable, for example, the display of images generated by electronic system800. Output devices that may be used with the output device interface806may include, for example, printers and display devices, such as a liquid crystal display (LCD), a light emitting diode (LED) display, an organic light emitting diode (OLED) display, a flexible display, a flat panel display, a solid state display, a projector, or any other device for outputting information. One or more implementations may include devices that function as both input and output devices, such as a touchscreen. In these implementations, feedback provided to the user can be any form of sensory feedback, such as visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input.

Finally, as shown inFIG.8, the bus808also couples the electronic system800to one or more networks and/or to one or more network nodes, through the one or more network interface(s)816. In this manner, the electronic system800can be a part of a network of computers (such as a local area network (LAN), a wide area network (WAN), an Intranet, or a network of networks, such as the Internet). Any or all components of the electronic system800can be used in conjunction with the subject disclosure.

Phrases such as “an aspect,” “the aspect,” “another aspect,” “some aspects,” “one or more aspects,” “an implementation,” “the implementation,” “another implementation,” “some implementations,” “one or more implementations,” “an embodiment,” “the embodiment,” “another embodiment,” “some embodiments,” “one or more embodiments,” “a configuration,” “the configuration,” “another configuration,” “some configurations,” “one or more configurations,” “the subject technology,” “the disclosure,” “the present disclosure,” and other variations thereof and alike are for convenience and do not imply that a disclosure relating to such phrase(s) is essential to the subject technology or that such disclosure applies to all configurations of the subject technology. A disclosure relating to such phrase(s) may apply to all configurations, or one or more configurations. A disclosure relating to such phrase(s) may provide one or more examples. A phrase such as an aspect or some aspects may refer to one or more aspects and vice versa, and this applies similarly to other foregoing phrases.