Shared memory switch fabric system and method

A system and method of transferring cells through a router includes writing one or more of the plurality of cells, including a first cell, of a packet from an ingress stream of an ingress writer to a central buffer, storing a packet identifier entry in the first egress reader scoreboard in each of the plurality of egress readers, the packet identifier entry including a packet identifier, a valid bit, a hit bit and a write cell count, wherein the valid bit is configured to indicate that the packet identifier entry is valid, the hit bit is configured to indicate that no cells in the packet have been read from the central buffer and the write cell count equals the number of cells in the packet written to the central buffer, and reading the packet from the central buffer as a function of the packet identifier entry.

TECHNICAL FIELD

The disclosure relates to computer networks and, more particularly, to transferring packets within computer networks.

BACKGROUND

A computer network is a collection of interconnected computing devices that can exchange data and share resources. In a packet-based network, such as an Ethernet network, the computing devices communicate data by dividing the data into variable-length blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form.

Certain devices, referred to as routers, maintain routing information representative of a topology of the network. The routers exchange routing information so as to maintain an accurate representation of available routes through the network. A “route” can generally be defined as a path between two locations on the network. Upon receiving an incoming data packet, a router examines information within the packet, often referred to as a “key,” to select an appropriate next hop to which to forward the packet in accordance with the routing information.

A variety of routers exist within the Internet. Network Service Providers (NSPs), for example, maintain “edge routers” to provide Internet access and other services to the customers. Examples of services that the NSP may provide include Voice over IP (VoIP), access for Asynchronous Transfer Mode (ATM) or frame relay communications, Internet protocol (IP) data services, and multimedia services, such as video streaming. The edge routers of the NSPs often communicate network traffic to high-speed “core routers,” which may be generally viewed as forming the backbone of the Internet. These core routers often include substantially more processing resources than the edge routers, and are designed to handle high volumes of network traffic.

In some examples, a core router includes one or more planes of switch fabric. In some such examples, each switch fabric includes a crossbar switch which connects two or more ingress ports to two or more egress ports. In some such examples, input queues received cells from the ingress ports and transfer the cells to output queues associated with each egress port. In some examples, a shared memory provides temporary cell storage when one or more output queues reaches capacity. In some such examples, when there is no congestion at the output queue the shared memory is bypassed via a crossbar switch.

In some examples, a core router or another router or switching device may employ a distributed, multi-stage switch fabric architecture, in which network packets traverse multiple stages of the switch fabric located in distributed forwarding components of the router to travel from an ingress point of the switch fabric to an egress point of the switch fabric. As one example, a switch fabric may be implemented as a single multi-stage Clos switch fabric, which relays communications across the stages of the switch fabric. A typical multi-stage Clos switch fabric has a plurality of switches interconnected to form a plurality of stages. In a typical arrangement, the switch fabric includes an ingress (or “first”) stage, one or more intermediate stages, and an egress (or “final”) stage, with each stage having one or more switches (e.g., crossbar switches—often referred to more simply as “crossbars”). Moreover, the switch fabric may be implemented such that the switches are arranged as multiple parallel fabric planes that each provide independent forwarding from ingress ports to egress ports through the multiple stages, one or more of which may be treated as a spare fabric plane. In other words, each of the parallel fabric planes may be viewed as an independent portion of the multi-stage Clos switch fabric, where each plane provides switching redundancy.

SUMMARY

In general, techniques are described for transferring cells through a switch fabric from an ingress port to output queues associated with egress ports. In one example, the switch fabric includes a shared memory and a low latency path that bypasses shared memory. In one such example, the shared memory provides temporary cell storage when one or more output queues reaches a predefined threshold.

In one example, a method of routing a packet having a plurality of cells from an ingress stream associated with a first ingress writer to a first egress reader includes associating a first egress reader scoreboard in each of a plurality of egress readers with the first ingress writer, the plurality of egress readers including the first egress reader, the first egress reader scoreboard including a plurality of packet identifier entries, writing one or more of the plurality of cells, including a first cell, of the packet from an ingress stream of the first ingress writer to a central buffer, writing a packet identifier and a write cell count to one of the packet identifier entries in the first egress reader scoreboard in each of the plurality of egress readers, the packet identifier associated with the packet and the write cell count indicating the number of cells in the packet written to the central buffer, receiving notification of the packet at the first egress reader, wherein the notification includes the packet identifier of the packet, selecting a packet identifier entry with a packet identifier that matches the packet identifier of the notification, while cells of the packet remain to be written by the first ingress writer to the central buffer and while the write cell count of the selected packet identifier entry is greater than a read cell count indicating the number of cells in the packet read by the first egress reader from the central buffer, transferring the next cell in the packet from the central buffer to the first egress reader and incrementing the read cell count, and after all cells of the packet have been written by the first ingress writer to the central buffer, transferring any cells in the packet remaining in the central buffer to the first egress reader.

In another example, a router includes a plurality N of ingress writers, wherein each ingress writer includes P ingress streams, a plurality M of egress readers, wherein each egress reader includes a separate egress reader scoreboard for each of the N ingress writers and wherein each egress reader includes Q egress streams, a central buffer connected to the ingress writers and the egress readers, wherein the ingress writers write packet cells from the ingress streams into the central buffer and the egress readers read packet cells from the central buffer to transmit on the egress streams, an egress scheduler connected to the ingress writers and the egress readers, wherein the egress scheduler receives a notification from an ingress writer that the ingress writer has written cells of a packet to the central buffer and distributes the notification to one or more of the egress readers and wherein, when storing a packet in the central buffer, each ingress writer stores a packet identifier entry in the egress reader scoreboard associated with the ingress writer in each of the plurality of egress readers, the packet identifier entry including a packet identifier, a valid bit, a hit bit, an egress stream number and a write cell count, wherein the valid bit is configured to indicate that the packet identifier entry is valid, the hit bit is configured to indicate that no cells in the packet have been read from the central buffer and the write cell count equals the number of cells in the packet written to the central buffer, wherein, when reading a packet from the central buffer, the egress reader reads the first cell of the packet from the central buffer based on the packet identifier stored in the packet identifier entry associated with the packet, configures the hit bit in the packet identifier entry containing the packet identifier to indicate that the packet associated with the packet identifier entry is being read by the egress reader, stores an egress state in an egress state table, the egress state including a chase bit indicating that the packet is being read by the egress reader while it is being written into the central buffer and a read cell count indicating the number of cells in the packet read from the central buffer by the egress reader, increments the read cell count each time a cell in the packet is read from the central buffer based on a valid entry in the egress reader scoreboard and reads the next cell in the packet from the central buffer as long as the write cell count is greater than the read cell count or the last cell in the packet has been written to the central buffer.

In another example, a method includes associating a first egress scoreboard in each of a plurality of egress readers with a first ingress writer, the plurality of egress readers including the first egress reader, writing one or more of the plurality of cells, including a first cell, of a packet from an ingress stream of the first ingress writer to a central buffer, storing a packet identifier entry in the first egress reader scoreboard in each of the plurality of egress readers, the packet identifier entry including a packet identifier, a valid bit, a hit bit, an egress stream number and a write cell count, wherein the valid bit is configured to indicate that the packet identifier entry is valid, the hit bit is configured to indicate that no cells in the packet have been read from the central buffer and the write cell count equals the number of cells in the packet written to the central buffer, writing a next cell from the packet to the central buffer, wherein writing a next cell includes incrementing the write cell count in the packet identifier entry associated with the packet, and writing an end of packet cell from the packet to the central buffer, wherein writing an end of packet cell includes marking the packet identifier entry as invalid.

In another example, a method includes receiving notification of a new packet being stored in a central buffer, the notification including a packet identifier, searching an egress reader scoreboard having a plurality of packet identifier entries to determine if the packet identifier is present in a packet identifier entry in the egress reader scoreboard and that the packet identifier entry with the matching packet identifier has not yet been hit; in response to determining the packet identifier is present in a packet identifier entry in the scoreboard and that the packet identifier entry with the matching packet identifier has not yet been hit: configuring a hit bit in the packet identifier entry containing the packet identifier to indicate that the packet associated with the packet identifier entry is being read by an egress reader, storing an egress state in an egress state table, the egress state including a chase bit indicating that the packet is being read by an egress reader while the packet is being written into the central buffer by an ingress writer and a read cell count indicating the number of cells in the packet read from the central buffer, incrementing the read cell count each time a cell in the packet is read from the central buffer based on a valid packet identifier entry in the egress reader scoreboard; and reading the next cell in the packet from the central buffer as long as the write cell count is greater than the read cell count or the last cell in the packet has been written to the central buffer.

In yet another example, a router includes a plurality N of ingress writers, wherein each ingress writer includes P ingress streams; a plurality M of egress readers, wherein each egress reader includes a separate egress reader scoreboard for each of the N ingress writers, wherein each egress reader scoreboard includes a plurality of packet identifier entries and wherein each egress reader includes Q egress streams; and a central buffer connected to the ingress writers and the egress readers, wherein the ingress writers write packet cells from the ingress streams into the central buffer and the egress readers read packet cells from the central buffer to transmit on the egress streams, wherein each ingress writer: writes one or more of the plurality of cells, including a first cell, of a packet to a central buffer, stores a packet identifier entry in the egress reader scoreboard associated with the ingress writer in each of the plurality of egress readers, the packet identifier entry including a packet identifier, a valid bit, a hit bit, an egress stream number and a write cell count, wherein the valid bit is configured to indicate that the packet identifier entry is valid, the hit bit is configured to indicate that no cells in the packet have been read from the central buffer and the write cell count equals the number of cells in the packet written to the central buffer, writes a next cell from the packet to the central buffer, wherein writing a next cell includes incrementing the write cell count in the packet identifier entry associated with the packet, and writes an end of packet cell from the packet to the central buffer, wherein writing an end of packet cell includes marking the packet identifier entry as invalid, and wherein each egress reader, when it receives a notification, including a packet identifier, of a new packet being stored in the central buffer: searches the egress reader scoreboards of the egress reader to determine if the packet identifier is present in a packet identifier entry in the egress reader scoreboard and that the packet identifier entry with the matching packet identifier has not yet been hit; if the packet identifier is not present in a packet identifier entry in the scoreboard or the packet identifier entry with the matching packet identifier has been hit, reads the new packet from the central buffer without consulting the egress reader scoreboard; and if the packet identifier is present in a packet identifier entry in the scoreboard and the packet identifier entry with the matching packet identifier has not yet been hit: configures a hit bit in the packet identifier entry containing the packet identifier to indicate that the packet associated with the packet identifier entry is being read by an egress reader, stores an egress state in an egress state table, the egress state including a chase bit indicating that the packet is being read by an egress reader while the packet is being written into the central buffer by an ingress writer and a read cell count indicating the number of cells in the packet read from the central buffer, increments the read cell count each time a cell in the packet is read from the central buffer based on a valid packet identifier entry in the egress reader scoreboard, and reads the next cell in the packet from the central buffer as long as the write cell count is greater than the read cell count or the last cell in the packet has been written to the central buffer.

Like reference characters denote like elements throughout the figures and text.

DETAILED DESCRIPTION

In general, techniques are described for transferring cells through a router from an ingress port to output queues associated with egress ports. Cells may be transferred through a switch fabric or, in some cases, may be transferred through the router without passing through the switch fabric. In order to reduce latency when traffic is not going through the router, techniques are described for cut-through routing through a central buffer to the egress ports.

FIG. 1is a block diagram illustrating an example network environment in which service provider network includes a router configured in accordance with techniques described in this disclosure. In the example shown inFIG. 1, network environment2includes a service provider network6with one or more routers4and one or more edge routers5, each configured in accordance with techniques described in this disclosure. For purposes of example, the principles of the invention are described with respect to a simplified network environment2ofFIG. 1in which chassis router4communicates with edge routers5A,5B and5C (“edge routers5”) to provide customer networks8A-8D (“customer networks8”) with access to service provider network6. Router4may exchange routing information with edge routers5in order to maintain an accurate representation of the topology of network environment2. Router4may include a plurality of cooperative routing components operating as a single node within service provider network6. In addition, while described with respect to router4, the techniques disclosed herein are also applicable to single chassis routers and to other contexts in which a switch fabric is employed.

Although not illustrated, service provider network6may be coupled to one or more networks administered by other providers, and may thus form part of a large-scale public network infrastructure, e.g., the Internet. Consequently, customer networks8may be viewed as edge networks of the Internet. Service provider network6may provide computing devices within customer networks8with access to the Internet, and may allow the computing devices within customer networks8to communicate with each other. In another example, service provider network6may provide network services within the core of the Internet. In either case, service provider network6may include a variety of network devices (not shown) other than router4and edge routers5, such as additional routers, switches, servers, or other devices.

In the illustrated example, edge router5A is coupled to customer network8A via access link9A and to customer network8B via access link9B, edge router5B is coupled to customer network8C via access link9C, and edge router5C is coupled to customer networks8D via access link9D. Customer networks8may be networks for geographically separated sites of an enterprise. Customer networks8may include one or more computing devices (not shown), such as personal computers, laptop computers, handheld computers, workstations, servers, switches, printers, customer data centers or other devices. The configuration of network environment2illustrated inFIG. 1is merely an example. Service provider network6may be coupled to any number of customer networks8. Nonetheless, for ease of description, only customer networks8A-8C are illustrated inFIG. 1. Many different types of networks besides service provider network may employ an instance of router4, including customer/enterprise networks, transport networks, aggregation or access networks, and so forth.

In some examples, router4includes multiple chassis (not shown inFIG. 1) that are physically coupled and configured to operate as a single router. In some such examples, router4appears as a single routing device to edge routers5of network environment2. For example, although router4may include a plurality of chassis, from the perspective of peer routers5, router4may have a single network address and may maintain single peer routing sessions for each routing protocol maintaining peer routing sessions with each of the edge routers5.

As described in further detail below, in some examples, the multiple routing nodes of router4forward packets, i.e., network traffic, on a data plane of router4using an internal multi-stage switch fabric7that interconnects fabric endpoints within the router to network interface cards (e.g., port interface cards) of the router. In the example ofFIG. 1, multi-stage switch fabric7switches data units from ingress ports of the network interface cards to the egress ports of the network interface cards to perform high-speed packet forwarding among and within the routing nodes of the router4. Multi-stage switch fabric7may represent a 3-stage Clos network, a 5-stage Clos network, or an n-stage Clos network for any value of n. In general, packets received at an ingress port are divided into one or more fixed-length cells for switching. However, in some instances packets may be divided into variable-length data units for switching or switched intact as respective data units. A “data cell” or “cell” refers to a smallest block of data that is passed through the multi-stage switch fabric7. The cell includes a header portion and a data portion. “Cell data” refers to data contained within a data portion of a cell. Additional details for example cell formats are described below with respect toFIG. 4. As used throughout this description unless specifically indicated otherwise, “cell” may refer to any data unit switched by a multi-stage switch fabric.

FIG. 2is a block diagram illustrating an example of a switching system in accordance with techniques described in this disclosure. In the example ofFIG. 2, a standalone routing node10includes a control unit7having a routing engine16. Standalone routing node10also includes forwarding engines20A through20N (“FEs20”) connected to a switch fabric18. FEs20may receive and send data via interface cards21A through21N (“IFCs21”) and IFCs22A through22N (“IFCs22”). In one example, IFCs21may be designated for receiving and sending packet-switched communications, and IFCs22may be designated for receiving and sending circuit-switched communications. In other embodiments, each of FEs20may comprise more or fewer IFCs. Switch fabric18provides an interconnect mechanism for forwarding data between FEs20for transmission over a network, e.g., the Internet.

Routing engine16maintains routing tables, executes routing protocols and controls user access to standalone routing node10. In this example, routing engine16is connected to each of FEs20by a dedicated link24, with may be an internal Ethernet link. For example, dedicated link24may comprise a 1000 Mbps Ethernet connection. Routing engine16maintains routing information that describes a topology of a network, and derives a forwarding information base (FIB) in accordance with the routing information. Routing engine16copies the FIB to each of FEs20. This allows the FIB in each of FEs20to be updated without degrading packet forwarding performance of standalone router10. Alternatively, routing engine16may drive separate FIBs which are copied to respective FEs20.

In a routing node, a “switch plane” is generally capable of providing a communication path between any two of FEs20. In this example, switch fabric18consists of multiple standalone switch planes19A through19M (“switch planes19”). In some embodiments, each of switch planes19is provided by one or more switch fabric chips on one or more separate, removable switch cards. Other routing nodes that implement the techniques described herein may comprise additional or fewer switch planes, including a single switch plane. A majority of the switch planes, e.g., switch planes19A-19D, may be active at any given time with data packets distributed over the active switch planes. The inactive switch plane(s) of switch fabric18serves as back-up switch plane(s) such that if one or more of the active switch planes goes offline, the back-up switch plane(s) automatically activate, and the bandwidth capacity of standalone router10is not diminished. The back-up switch plane(s) may be identical to the active switch planes and act as hot spare(s) to maintain bandwidth capacity in the event that one or more of the active switch planes fail. Each of switch planes19is operationally independent; therefore, standalone routing node10may continue to forward packets as long as at least one of switch planes19remain active, but possibly at a reduced bandwidth capacity.

As part of a standalone router, switch planes19form a standalone switch fabric18. That is, each of switch planes19is capable of providing a connection between any of FEs20within standalone routing node10. In this manner, switch planes19form a standalone switch fabric that enables packet forwarding between the plurality of FEs20of standalone routing node10. For example, switch fabric18may be provided by a set of removable switch cards, where each removable switch card provides a respective one of switch planes19.

An example flow-path of data packets through standalone routing node10is as follows. Initially, an incoming data packet is received by one of packet IFCs21, e.g., IFC21A, having a network interface for receiving data packets from a packet-based network link, such as an Ethernet link. Interfaces on IFC21A send packet data, such as a packet header, to a lookup module of FE20A for processing. The lookup module (not shown) determines a destination address, multicast forwarding tuple, or other keying information of the packet from the packet data and queries a forwarding information base (FIB) for a forwarding entry matching the keying information. A matching entry specifies the appropriate next hop interface for the packet. FE20A stores the packet for future processing in an input buffer. The input buffer is typically a form of dynamic RAM (e.g., DRAM, SDRAM, DDR2, RLDRAM, and the like) but may be another type of storage media. In some embodiments, the input buffer is shared among the various FEs20of routing node10as distributed buffer memory. In some embodiments, interfaces of IFCs21are implemented as high-speed, on-chip memory within one or more forwarding integrated circuits, and the input buffer is provided by off-chip DDR2 coupled to the forwarding integrated circuits by a data bus.

The input buffer stores network packets received by IFC21A, that is, those packets for which FE20A is the ingress one of FEs20. As a result, packets stored in FE20A are input queued and wait for scheduling to be switched across switch fabric18to the appropriate one or more egress FEs20. The input buffer may provide a variable-size buffer for each destination.

In this example, FE20A segments the inbound data packet into multiple cells, e.g., into sixty-four-byte data cells. FE20A may mark the cells with an indication that the cells are “packet” cells, e.g., by setting a special data bit in a cell header. The cell header may also indicate a priority of an associated packet, for purposes of flow control within the switch fabric. FE20A selects a queue for enqueuing the packet based on the next hop interface determined by the lookup module. FE20A performs flow control for packet switching communications, e.g., by sending a request through switch fabric18to the egress FE20for sending the number of cells corresponding to the packet. The egress FE20may respond with a grant. Upon receiving the grant, FE20A dequeues the packet cells and transfers the cells of the packet across the active switch planes to the correct egress FE. During this process, the active switch planes having fabric chips with ports designated for packet switching will forward the packet cells to the egress FE. When the packet cells arrive at the egress FE, e.g., FE20N, they are written into egress memory and reassembled into the original packet. The data packet is then transmitted into the network (not shown) via one of IFCs21or22, e.g., IFC21N. By dividing the data packet into cells and evenly transmitting the packet on a cell-by-cell basis across the switch planes, a FE may load-balance the packet-based traffic across each of the active switch planes having interconnects currently configured for packet-based switching.

Control unit12may be implemented solely in software, or hardware, or may be implemented as combinations of software, hardware, or firmware. For example, control unit12may include one or more processors which execute software instructions. For example, control unit12may comprise a processor, such as one or more programmable processors, microprocessors, application specific integrated circuits, field programmable gate arrays, digital signal processors, or other equivalent integrated or discrete logic circuitry. Control unit12may comprise one or more processors that execute software instructions, such as those used to define a software or computer program, stored to a computer-readable storage medium, such as a storage device (e.g., a disk drive, or an optical drive), or memory (e.g., a Flash memory, random access memory, or RAM) or any other type of volatile or non-volatile memory that stores instructions (e.g., in the form of a computer program or other executable) to cause a programmable processor to perform the techniques described herein. Alternatively, control unit12may comprise dedicated hardware, such as one or more integrated circuits, one or more Application Specific Integrated Circuits (ASICs), one or more Application Specific Special Processors (ASSPs), one or more Field Programmable Gate Arrays (FPGAs), one or more Digital Signal Processors (DSPs) or any combination of the foregoing examples of dedicated hardware, for performing the techniques described herein.

FIG. 3is a block diagram illustrating an example of a switching system according to techniques described herein. Switch fabric28(“fabric28”) of switching system26may represent an example instance of switch fabric7of the router4ofFIG. 1. In some examples, fabric endpoints30A,30B (collectively, “fabric endpoints30”) of switching system26are separately coupled to each of fabric planes32A-32K of multi-stage switch fabric28to operate as sources and/or destinations of data units (e.g., cells) switched by fabric28. In the illustrated example, fabric endpoint30A ingresses, originates, or otherwise sources packets36for switching via switch fabric28to a fabric endpoint30B that egresses, consumes, or otherwise sinks packets36.

Although each of fabric endpoints30typically operates as both a source and a destination for cells, any of fabric endpoints30may be either a source or a destination for cells in various instances. In some examples, fabric endpoints30may each represent a packet forwarding engine or other forwarding unit such that fabric endpoints30collectively implement a distributed forwarding plane for a packet switching device (e.g. router4). In some examples, fabric endpoints30may represent fabric interfaces for servers or other hosts (e.g., virtual machines) that exchange packets for a distributed application via fabric28. Fabric endpoints30may include respective switch fabric interfaces or “switch interfaces” (SIs—not shown) to provide queuing for cells being switched via fabric28, among other operations.

In this example, switch fabric28includes a plurality of operationally independent, parallel switch fabric planes32A-32K (illustrated as “fabric planes32A-32K”) and referred to herein collectively as “fabric planes32”). The number of fabric planes32may be any number, dependent upon the respective capacities of the fabric planes32and the fabric bandwidth needed. Fabric planes32may include 4, 5, or 18 planes, for instance. In some examples, fabric plane32K operates as a backup or spare fabric plane to the remaining fabric planes32. Each of fabric planes32includes similar components for implementing an independent Clos or other multi-stage switch network (e.g., Benes network) to provide independent switching bandwidth to fabric endpoints30, said components and functionality being described hereinafter primarily with respect to fabric plane32A. Fabric planes32are operationally independent in that a failure of one of fabric planes32does not affect the switching ability of the remaining, operational fabric planes. Each of fabric planes32may provide non-blocking connectivity. Additional details regarding an example of a multi-stage switch fabric having a plurality of switch planes are found in Pradeep S. Sindhu, U.S. Pat. No. 7,102,999, entitled “Switching Device” and filed Nov. 24, 1999, the description of which is incorporated herein by reference. An example of a router having a multi-stage switch fabric may be found in Pradeep S. Sindhu, U.S. Patent Publ. No. 2008/0044181 A1, entitled “Multi-chassis router with multiplexed optical interconnects” and published Feb. 21, 2008, the descriptions of which are incorporated herein by reference. Other switch fabric architectures are also possible.

Each of fabric planes32includes an input port coupled to fabric endpoint30A and an output port coupled to fabric endpoint30B. Although only one ingress fabric endpoint30A and one egress fabric endpoint30B is illustrated for simplicity, each fabric plane32typically includes multiple input ports and output ports coupled to respective fabric endpoints. When a fabric endpoint30A obtains a packet, the fabric endpoint30A performs a lookup operation to determine which fabric endpoint30B (in this example) is a destination for the packet. Obtaining a packet may refer to receiving a packet from the network or host, or originating a packet, for example. Fabric endpoint30A optionally divides the packet into cells and forwards the packet/cells across fabric28to fabric endpoint30B. Fabric endpoint30A selects different fabric planes32to switch the cells to distribute the bandwidth load across the fabric planes32.

Fabric endpoints30A,30B may employ a request/grant protocol to transmit a data cell across fabric28. In such cases, source fabric endpoint30A transmits a request across fabric28to the destination fabric endpoint30B. In one example approach, fabric endpoint30A transmits each such request across a different one of fabric planes32in a round-robin or other balancing order to fairly distribute the transport load. In response to receiving the request, fabric endpoint30B transmits a grant to the fabric endpoint30A across the same fabric plane32on which fabric endpoint30B received the corresponding request. In response to receiving the grant, fabric endpoint30A transmits the data cell to the fabric endpoint30B across the same fabric plane32on which fabric endpoint30A issued the corresponding request.

As noted above, each of fabric planes32may include similar components to perform similar multi-stage switch functionality. Fabric plane32A, as an example, includes a plurality of fabric chips34coupled by fabric chip-to-chip links (CCLs—not shown) to implement a multi-stage switch fabric for the fabric plane32A. Fabric chips34may be distributed among various switching devices, chassis, etc., of the switching system26. Each of fabric chips34may include an application-specific integrated circuit (ASIC) and may be referred to as a “fabric ASIC.”

In some examples, fabric endpoint30A includes fault detection module (not shown) used to generate and receive self-ping cells to verify per-plane connectivity for the fabric endpoint30A with respect fabric planes32. Example approaches to failure detection and handling in a router and switch fabric are described in “Multi-Stage Switch Fabric Fault Detection and Handling,” U.S. patent Ser. No. 14/623,083, filed Feb. 16, 2015, the description of which is incorporated herein by reference.

While described for purposes of illustration with respect to a router having distributed line-card chassis, each coupled to one or more switch card chassis, the techniques of this disclosure are applicable to any single or multi-chassis network device or network switching fabric that switches data units among a large number of fabric endpoints.

FIG. 4is a block diagram illustrating an example data cell format according to techniques of this disclosure. Different cell types according to data cell50define operations for fabric endpoints20and different stage switches in a multistage switch fabric, as described in further detail below. Data cell50includes a cell header51and cell payload64. Cell header51includes the following fields: cell size52, cell type54, sequence number (SEQ NO.)56, destination identifier (DST ID)58, and source identifier60(SRC ID). Various example implementations for cell header51may rearrange fields, include more or fewer fields, and so forth.

Cell size52specifies the size of the cell payload64or, in some cases, the size of data cell50including both the cell header51and the cell payload64. An example header size is 24 bytes. Example cell sizes include 96, 112, 128, 144, 160 and 176 bytes. Cell type54identifies the type of the cell, including the type of fabric chip (e.g., a first stage, intermediate/second stage, third/final stage, or fabric endpoint) that is to consume and process the cell. Sequence number56identifies a sequence number for the cell. Cell destination identifier58and cell source identifier58identify the destination fabric endpoint and source fabric endpoint for the cell, respectively. The data payload64for data cell50is typically packet data for packets switched by the switching system, whether a packet switch or data center fabric for instance. Payload64may, however, be used in some instances to transfer other information such as, for example, indications of connectivity faults or fabric faults in a fabric plane of the switching system.

FIG. 5is a block diagram depicting an application-specific integrated circuit (ASIC) configured to implement a switch in accordance with techniques described in this disclosure. ASIC410represents hardware-based logic and may include a programmable integrated circuit. ASIC410may represent an example of a fabric chip24and, in some examples, implements crossbar switch400for a stage of a multi-stage switching fabric.

Crossbar switch400has input ports402A-4025(collectively, “input ports402”) each capable of spraying cells via a full mesh to each of output ports404A-404T (collectively, “output ports404”). Switching module412is programmed with spray mask416that identifies output ports404usable for reaching destination fabric endpoints20. Fault handling module414may be configured to detect link faults and to handle fault notification cells and generate and send fault notification cells/messages. Although individual crossbars are described herein, respectively, as components in the first, second, and third stages of multi-stage switching fabrics, a single generic type of crossbar switch may be used for all three stages by configuring the operational mode of the ASIC410accordingly.

FIG. 6is a block diagram illustrating cut-through routing according to techniques of this disclosure. In the example ofFIG. 6, N IngressWriters450are connected to a central buffer452, a link list454and an EgressScheduler456. In one example approach, each IngressWriter450enqueues the packet notification to EgressScheduler456after a cell of the packet is written to the CentralBuffer452. In another example approach, each IngressWriter450enqueues the packet notification to EgressScheduler456after two cells of the packet are written to the CentralBuffer452. The packet notification contains the pointer to the first-cell as the packet-identifier. The EgressScheduler456may then send the packet to the EgressReader458and the EgressReader458can start reading the packet from the CentralBuffer452while the IngressWriter450is still writing the packet.

In one example approach, EgressReader458reads cells from central buffer452soon after the cells are written by IngressWriter450. Such an approach ensures that downstream MAC do not “underrun” and, in addition, ensures low latency in this mode.

In one example approach, CentralBuffer452deallocates the cells after they are read by EgressReader458. The deallocated cell, which can also be the first cell, can be reused by the IngressWriter450. In such an approach, this causes a situation where multiple packets can be simultaneously written with the same packet-identifier and some of those packets may also be simultaneously read by EgressReader458. Techniques are described to address this challenge.

In one example approach, for each cut-through packet, each IngressWriter450advertises the number of cells it has written (and linked) to every EgressReader's scoreboard using a packet-identifier (the first-cell-address of the packet). The scoreboard is conceptually a CAM, with the first-cell-address as the match. The data is the count of the number of cells already written for the packet (call this the “Write Cell Count”, WCC). Each EgressReader458includes multiple scoreboards, one scoreboard for each IngressWriter450. Each scoreboard includes as many entries as the number of input streams in the IngressWriter450. In one example approach, each IngressWriter450can complete at most one cell per cycle and each IngressWriter450can update one entry in each EgressReader's scoreboard with each cell written. Each ingress Stream completely writes a packet before proceeding to the next packet. Upon writing the first cell of a packet the entry is validated (valid=1) and upon writing the last cell of a packet, the entry is deleted from the scoreboard (valid=0).

In one example approach, each EgressReader458uses a work-conserving time-division multiplexing (TDM) arbitration among streams, where the TDM guarantees that each stream receives a fair share of service opportunities, and operates with significant speedup. When a stream gets selected by the arbitration, the EgressReader458reads one cell from the CentralBuffer452. A packet is then read one cell at a time, with each read cell's address deallocated, i.e. it can be re-used by the CentralBuffer452, after it is read. In one example approach, each EgressReader458keeps a running count (“Read Cell Count” or “RCC”)) of the number of cells of the packet read so far, for each active packet context (one per stream). EgressReader458also maintains a state “chasing” (one per stream) which indicates whether the packet it is reading is currently also being written by the IngressWriter450.

It should be noted that the above scheme may be extended to cover sending packets to and from the fabric. That is, EgressReader458could also be sending packets across the fabric, and IngressWriter450could be receiving packets from the fabric, and the same cut-through scheme may be used between IngressWriter450and EgressReader458, at both ends of the fabric.

FIG. 7is a block diagram illustrating a scoreboard based approach to cut-through routing according to techniques of this disclosure. In the example shown inFIG. 7, an EgressReader scoreboard500stores a packet identifier502, a valid bit504, a hit bit506, an eg_stream number508associated with a particular eg_stream, and a write cell count (WCC)510. In one example approach, each EgressReader458includes one ER scoreboard500for each IngressWriter. In the example shown inFIG. 6, for instance, each EgressReader458includes N scoreboards500. In one such approach, there are five IngressWriters450and five EgressReaders458, or N=5, such as is shown inFIG. 8below. In one example approach, the packet identifier and its associated status bits are written to a location in ER scoreboard500associated with a particular ig_stream number.

In one example approach, when a stream receives its TDM slot for an ongoing packet, EgressReader458determines if it is starting a new packet. If EgressReader458is starting a new packet, then EgressReader458searches through the ER scoreboard500to determine if it is reading a packet which is currently being written, using the packet-identifier.

If EgressReader458misses in the ER scoreboard500for a packet, it can assume that all cells of the packet have been successfully written. This is so because the packet was enqueued much earlier, its entry was overwritten by another packet from the same ingress stream and so is no longer in the ER scoreboard500. In the event of a miss, EgressReader458notes that it is not-chasing the IngressWriter450and reads the subsequent cells of the packet without consulting the ER scoreboard500.

If the EgressReader's search finds a hit in the ER scoreboard500for a packet, it changes the packet identifier entry512associated with the ig_stream so that hit bit506equals 1. As discussed below, EgressReader458makes a note that it is chasing a particular packet and notes the ingress stream number that is the source of the packet. For all subsequent cells of the packet the EgressReader458determines if it is still chasing the packet which the IngressWriter450is writing. If so, it just reads the entry512in the ER scoreboard500corresponding to the ingress stream. It reads the packet identifier entry512to ensure that this next cell position of the packet has already been written. In one example approach, EgressReader458checks that WCC>RCC. If WCC<=RCC, EgressReader458gives up the service opportunity, which may then be reclaimed by another stream which is not subject to cut-through pacing (the “work conserving” aspect). EgressReader458may try again on the stream's next TDM service opportunity.

In one example approach, if the IngressWriter450writes the last cell of a packet, it notifies the EgressReader458about it. The EgressReader458then reads the rest of the packet as if is not-chasing the IngressWriter450and hence does not consult ER scoreboard500. This is because the packet identifier entry512will be re-written by a new packet from the same ingress stream, which would restart the WCC field510of that entry.

Since the first-cell address is deallocated when it is read, the first-cell can be reused and multiple packets can be written simultaneously by the writer with the same packet-identifier. (A point to note here is that the first-cell of a packet is reused only when the read for the packet has started. To handle this challenge, in one example approach, the CAM search of ER scoreboard500done by EgressReader458only searches entries512which are not being chased by another egress stream (hit=0) and which are still being written by the IngressWriter450(valid=1). This way we can only have at most one hit in the ER scoreboard500.

One advantages of this scheme is that the approach includes robustness for keeping the IngressWriters450and EgressReaders458in sync; there is no possibility of “underrun” between the IngressWriters450and EgressReaders458, even if the IngressWriters450slow down for (unusual) reasons such as uneven bank distribution in central buffer452resulting in reduced write-bandwidth, or exceeding the burst CAM capacity in link list buffer454.

Such an approach pushes all potential cut-through failures to the edges of the chip: if one designs for backpressure from the central buffer453and the link list buffer454to IngressWriters450, then any slowdown would push back into the IBUFs, and eventually (in an extreme case) result in packet drops at entrance to IBUF. A severe slowdown the in-progress packet would simply be underrun at the egress MAC and get aborted on the wire.

The above approach does not require a special central buffer interface to deallocate the packet-identifier (the first-cell-address of the packet) at the end of the packet. The Central Buffer452may deallocate the cells as they are read by the EgressReader458. The deallocated cell, which can also be the first-cell, can be reused and can be the packet-identifier for another packet while the original packet is being read.

FIG. 8is a block diagram illustrating a cut-through routing according to techniques of this disclosure. In the example shown inFIG. 8, each IngressWriter450is associated with a separate ER scoreboard500in each EgressReader458. In addition, each EgressReader458includes an egress state table520that tracks the status of each ig_stream being written to ER scoreboard500.

In one example approach, each ER scoreboard500is 32 deep, as deep as the number of ig_streams. In one such example approach, the IngressWriter450provides a valid indication each time a cell is written along with the ig_stream, packet-identifier and eop (end of packet) indication. Each EgressReader458has one interface from each IngressWriter450.

If the EgressReader458wants to read a cell, then it takes action based on cell type, i.e., sop (start of packet) or non-sop. If it is a sop cell it searches the ER scoreboards500. If it is a non-sop cell and the egress_state indicates that the EgressReader458is chasing the packet, then it reads an entry in the ER scoreboard500to get the WCC and then compares that to the RCC to make a decision. If it is a non-sop cell and the egress_state indicates that it is not-chasing the packet, then the decision may be to read the cell of the packet.

FIG. 9is a table illustrating egress state table520according to techniques of this disclosure. In the example shown inFIG. 9, egress state table520includes an entry530for each egress stream; egress state table520is indexed in one example approach by egress stream number. In one example approach, each entry includes a chasing bit522, an IngressWriter number524identifying the IngressWriter450associated with the ingress stream, the ingress stream number526and a read cell count (RCC)528. At reset, all packet identifier entries512are set to valid=0 and hit=0 state and all egress_state entries530have chasing=1. On a non-end-of-packet cell write from an IngressWriter, the corresponding entry512in the ER scoreboard500may be changed to valid=1 and WCC++.

On an eop cell write from an IngressWriter, if the write cell was an eop cell and the packet identifier entry had valid=1 and hit=1 then the egress_state530for the eg_stream as stored in the packet identifier entry is changed to chasing=0 irrespective of the original state of the packet identifier entry512the corresponding entry512in the ER scoreboard500is changed to valid=0, hit=0 and WCC=0.

On a sop cell read from EgressReader, when the egress side reads a sop cell then the EgressReader458does a CAM search. In this step the search is done on packet identifier entries512which have valid=1 and hit=0. In one example approach, if a match is found in the CAM search (i.e., a CAM search “hit”), EgressReader458changes the packet identifier entry with hit=1, updates the eg_stream, and changes the egress_state with chasing=1 and stores the IngressWriter# and ig_stream# for that eg_stream. Else, if no match is found in the CAM search (i.e., a CAM search “miss”) then EgressReader458changes the egress_state to chasing=0.

On a non-sop cell read from EgressReader458, if the EgressReader wants to read a non-sop cell, then it reads the chasing bit. If chasing=1, then EgressReader458has a match at sop, the packet is still being written and the read side should access the corresponding entry in the ER scoreboard to read the WCC, i.e. CAM[IngressWriter#][ig_stream#].

If chasing=0, i.e. not-chasing, then EgressReader458did not get a match at sop or EgressReader458got a match at sop but the packet was completely written by the IngressWriter450in the meanwhile. If chasing=0 then a read from Central Buffer452can proceed. If, however, chasing=1 then EgressReader458reads the packet identifier entry512corresponding to IngressWriter# and ig_stream# and finds WCC510. If RCC528is less than WCC510then a read from Central Buffer452can proceed. Otherwise, the read needs to be done at a later time.

FIG. 10illustrates a state machine representation of transitions of the valid bit and the hit bit in the ER scoreboard according to techniques of this disclosure. In the example approach ofFIG. 10, state machine600starts in state602and remains there until a non-eop cell is written to central buffer452. While in state602, valid bit504and hit bit506both equal zero. When a non-eop cell is written to central buffer452, control moves to state604, and valid bit504is set to 1. Control remains in state604until an end-of-packet is written to central buffer452or a start of packet cell is read from central buffer452. If an end-of-packet is written to central buffer452before the start of packet cell is read by the EgressReader, control returns to602and both valid bit504and hit bit506are set to zero.

If a start-of-packet is read from central buffer452before the end-of-packet is written to central buffer452, control moves to606, and the RCC, valid bit504and hit bit506are all set to one. Control remains in state606until an end-of-packet cell from the packet is written to central buffer452, and then moves to state602, where valid bit504and hit bit506are both set equal to zero. While in state606, each time a packet cell is read, RCC is incremented (RCC+).

FIG. 11illustrates a state machine representation of the writing to a central buffer of cells of a cut-through packet according to techniques of this disclosure. At700, an IngressWriter450determines that a packet is a cut-through packet and, at702, writes the first one or more cells of the cut-through packet to central buffer452. At704, IngressWriter450writes information regarding the packet to a packet identifier entry512in ER scoreboard500at a location determined by the ig_stream number. The packet information includes a packet identifier502set to the address of the first cell in the central buffer, a valid bit504set to 1, a hit bit506set to 0, an egress stream number508and a write cell count (WCC)510equal to the number of cells written at that time. In some example approaches, IngressWriter450then notifies an EgressScheduler456of the start of a packet. EgressScheduler456may then send the packet to the EgressReader458and the EgressReader458may then start reading the packet from the CentralBuffer452while the IngressWriter458is still writing the packet.

At706, IngressWriter450writes the next cell of the cut-through packet to central buffer452and determines at708whether the cell written was an end of packet type cell. If the cell written was not an end of packet type cell, IngressWriter450updates packet identifier entry512to WCC+ and looks for the next cell at706.

If, however, IngressWriter450determines at708whether the cell written was an end of packet type cell, IngressWriter450updates packet identifier entry512at712to set WCC=0, valid bit504to 0 and hit bit506to 0, notifies the EgressReader458of the end of packet at714and moves to700. In one example approach, setting valid bit504to 0 at712serves to notify the EgressReaders458that an end of packet has arrived and control moves directly from712to700.

In one example approach, EgressReader458reads cells from central buffer452soon after the cells are written by IngressWriter450. Such an approach ensures that downstream MAC do not “underrun” and, in addition, ensures low latency in this mode.

In one example approach, each EgressReader458uses a work-conserving time-division multiplexing (TDM) arbitration among streams, where the TDM guarantees that each stream receives a fair share of service opportunities, and operates with significant speedup. When a stream gets selected by the arbitration, the EgressReader458reads one cell from the CentralBuffer452. A packet is then read one cell at a time, with each read cell's address deallocated, i.e. it can be re-used by the CentralBuffer452, after it is read. In one example approach, each EgressReader458keeps a running count (“Read Cell Count” or “RCC”)) of the number of cells of the packet read so far, for each active packet context (one per stream). EgressReader458also maintains a state “chasing” (one per stream) which indicates whether the packet it is reading is currently also being written by the IngressWriter450.

FIG. 12illustrates a state machine representation of the reading from a central buffer of cells of a cut-through packet according to techniques of this disclosure. At800, an EgressReader458receives notification of a new packet and moves to802to determine if the packet identifier associated with the packet has a match in ER scoreboard500that is valid (Valid=1) and not yet hit (Hit=0). (Once Hit is set to 1 by an EgressReader458, no other CAM search (at SOP) will match that entry512.) If EgressReader458does not find the packet identifier associated with the packet in ER scoreboard500, it can assume that that all cells of the packet have been successfully written. This may be because the packet was enqueued much earlier and its entry overwritten by another packet from the same ingress stream and so is no longer in the ER scoreboard500. In the event of a miss, the EgressReader458notes that it is not chasing the IngressWriter450and reads the subsequent cells of the packet without consulting ER scoreboard500.

If, at802, EgressReader458does find the packet identifier associated with the packet in ER scoreboard500, at806EgressReader458sets hit bit506to 1. At808, EgressReader458saves a chasing state in egress state table520at a location indexed by the egress stream number in packet identifier entry512, with chasing bit522set to 1 and the ingress stream number of the packet. For all subsequent cells of the packet the EgressReader458determines if it is still chasing the packet which the IngressWriter450is writing. If so, it just reads the entry512corresponding to the ingress stream to ensure that the next cell position of the packet has already been written and is available to be read. In one example approach, EgressReader458checks at810to determine if WCC>RCC. If WCC<=RCC, the EgressReader458moves to812and reads the next cell, checks at814to determine if an end of packet cell had been written by IngressWriter850and, if not, moves to810to fetch the next cell.

If, at814, EgressReader458determines that an end of packet cell had been written by IngressWriter850, control moves to816, where chasing bit522is cleared and then to804. All subsequent cells in the packet are read without consulting ER scoreboard500.

As noted above, in one example approach, each EgressReader458uses a work-conserving time-division multiplexing (TDM) arbitration among streams, where the TDM guarantees that each stream receives a fair share of service opportunities, and operates with significant speedup. When a stream gets selected by the arbitration, the EgressReader458reads one cell from the CentralBuffer452. A packet is then read one cell at a time, with each read cell's address deallocated, i.e. it can be re-used by the CentralBuffer452, after it is read. In one example approach, each EgressReader458keeps a running count (“Read Cell Count” or “RCC”)) of the number of cells of the packet read so far, for each active packet context (one per stream). EgressReader458also maintains a state “chasing” (one per stream) as noted above which indicates whether the packet EgressReader458is reading is currently also being written by the IngressWriter450.