# US 2020/0396158 A1 · Throughput in a crossbar network element by modifying mappings between time slots and ports

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0396158 A1
- Document ID: US20200396158A1
- Status: Published application
- Kind: A1
- Application number: 16/436,945
- Filed: 2019-06-11
- Published: 2020-12-17
- Earliest claimed: 2019-06-11
- Assignees: Mellanox Technologies Tlv Ltd.
- Applicants: Mellanox Technologies Tlv Ltd.
- Inventors: Ofir Merdler; George Elias; Yuval Shpigelman; Eyal Srebro; Sagi Kuks
- Web page: https://patentgrep.com/patent/US20200396158A1

## CPC

- H04L 45/60: Router architectures
- H04L 49/101: using crossbar or matrix
- H04L 49/25: Routing or path finding in a switch fabric
- H04L 49/3018: {Input queuing}
- H04L 49/3027: {Output queuing}
- H04L 49/50: Overload detection or protection within a single switching element
- H04L 49/9005: using dynamic buffer space allocation
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A network element includes output ports, a crossbar fabric and a scheduler. The output ports are organized in groups of multiple output ports selectable over predefined time slots in accordance with a cyclic mapping assigned to each group. In each time slot, the crossbar fabric routes to fabric outputs data received from the buffers via fabric inputs, in accordance with a routing plan. The scheduler determines and applies the routing plan for transmitting packets from the buffers to the communication network via the crossbar fabric and output ports. When in a given time slot, a required readout rate from a given buffer exceeds a maximum rate, the scheduler selects a group of the output ports to which the given buffer is routed in that time slot, and modifies the cyclic mapping for that group to reduce the required readout rate from the given buffer in the given time slot.

## Claims

### Claim 1

A network element, comprising:
multiple output ports coupled to a communication network and organized in M groups, each group comprising P output ports that are selectable over respective predefined time slots in accordance with a cyclic mapping between the time slots and the output ports for that group;
a crossbar fabric comprising M fabric outputs coupled respectively to the groups, and N fabric inputs coupled respectively to N buffers that store packets for transmission via the output ports, wherein in each time slot, the crossbar fabric is configured to receive data from the buffers via the fabric inputs, and route the data to the fabric outputs in accordance with a routing plan; and
a scheduler, configured to:
determine the routing plan over the time slots, and apply the routing plan for transmitting the packets from the buffers to the communication network via the crossbar fabric and the output ports;
in response to identifying that, in a given time slot, a required rate of readout of the packets from a given buffer exceeds a maximum rate supported by the given buffer, select a group of the output ports to which the given buffer is routed by the crossbar fabric in the given time slot, and modify the cyclic mapping for the selected group to produce a modified cyclic mapping that reduces the required rate of readout from the given buffer in the given time slot.

### Claim 2 (depends on 1)

The network element according to claim 1, wherein the given buffer comprises a number F of interfaces for simultaneously reading data of F different packets that are pending for transmission in the given buffer, and wherein the scheduler is configured to identify that the given buffer is oversubscribed by identifying that a number of simultaneous transmissions requested from the given buffer exceeds the number F.

### Claim 3 (depends on 2)

The network element according to claim 2, wherein the scheduler is configured to identify that the given buffer is oversubscribed by monitoring readout status of at least some of the N buffers, including the given buffer, wherein the readout status of a buffer is indicative of a number of transmission requests assigned to that buffer.

### Claim 4 (depends on 2)

The network element according to claim 2, wherein the scheduler is configured to identify that the given buffer is oversubscribed, by monitoring multiple transmission queues associated respectively with the multiple output ports, including a transmission queue of an output port to which the given buffer is routed, and checking whether a buffer routed to an output port of a monitored queue is oversubscribed.

### Claim 5 (depends on 2)

The network element according to claim 2, wherein the scheduler is configured to produce the modified cyclic mapping by applying a permutation among the time slots and the output ports of the cyclic mapping so that no other buffer that is routed to an output port of the selected group becomes oversubscribed by using the modified cyclic mapping.

### Claim 6 (depends on 1)

The network element according to claim 1, wherein the scheduler is configured to determine a permutation to be applied to the cyclic mapping for producing the modified cyclic mapping, and to apply the determined permutation to the cyclic mapping only after a delay that does not exceed a maximal predefined delay.

### Claim 7 (depends on 1)

The network element according to claim 1, wherein the scheduler is configured to modify the cyclic mapping by swapping a time slot assigned in the cyclic mapping to an output port to which the given buffer is routed, with a different time slot assigned in the cyclic mapping to another output port in the selected group.

### Claim 8 (depends on 7)

The network element according to claim 7, wherein the different time slot is assigned for transmission by another buffer, and wherein the scheduler is configured to verify that a required rate of readout from the another buffer is less than a maximum rate supported by the another buffer.

### Claim 9 (depends on 1)

The network element according to claim 1, wherein the scheduler is configured to apply the routing plan by coordinating, for each time slot, between (i) reading from a buffer using a specified read interface, (ii) applying a specified routing scheme within the crossbar fabric, and (iii) outputting the read data to a specified output port.

### Claim 10 (depends on 1)

The network element according to claim 1, wherein in response to identifying that a transmission queue associated with a given output port is congested, the scheduler is configured to give the group of output ports to which the given output port belongs, high priority to be selected for cyclic mapping modification.

### Claim 11

A method, comprising:
in a network element comprising multiple output ports coupled to a communication network and organized in M groups, each group comprising P output ports that are selectable over respective predefined time slots in accordance with a cyclic mapping between the time slots and the output ports for that group,
and a crossbar fabric comprising M fabric outputs coupled respectively to the groups, and N fabric inputs coupled respectively to N buffers that store packets for transmission via the output ports, wherein in each time slot,
receiving by the crossbar fabric data from the buffers via the fabric inputs, and routing the data to the fabric outputs in accordance with a routing plan;
determining the routing plan over the time slots, and applying the routing plan for transmitting the packets from the buffers to the communication network via the crossbar fabric and the output ports; and
in response to identifying that, in a given time slot, a required rate of readout of the packets from a given buffer exceeds a maximum rate supported by the given buffer, select a group of the output ports to which the given buffer is routed by the crossbar fabric in the given time slot, and modifying the cyclic mapping for the selected group to produce a modified cyclic mapping that reduces the required rate of readout from the given buffer in the given time slot.

### Claim 12 (depends on 11)

The method according to claim 11, wherein the given buffer comprises a number F of interfaces for simultaneously reading data of F different packets that are pending for transmission in the given buffer, and comprising identifying that the given buffer is oversubscribed by identifying that a number of simultaneous transmissions requested from the given buffer exceeds the number F.

### Claim 13 (depends on 12)

The method according to claim 12, wherein identifying that the given buffer is oversubscribed comprises monitoring readout status of at least some of the N buffers, including the given buffer, wherein the readout status of a buffer is indicative of a number of transmission requests assigned to that buffer.

### Claim 14 (depends on 12)

The method according to claim 12, wherein identifying that the given buffer is oversubscribed comprises monitoring multiple transmission queues associated respectively with the multiple output ports, including a transmission queue of an output port to which the given buffer is routed, and checking whether a buffer routed to an output port of a monitored queue is oversubscribed.

### Claim 15 (depends on 12)

The method according to claim 12, wherein modifying the cyclic mapping comprises producing the modified cyclic mapping by applying a permutation among the time slots and the output ports of the cyclic mapping so that no other buffer that is routed to an output port of the selected group becomes oversubscribed by using the modified cyclic mapping.

### Claim 16 (depends on 11)

The method according to claim 11, wherein modifying the cyclic mapping comprises determining a permutation to be applied to the cyclic mapping for producing the modified cyclic mapping, and applying the determined permutation to the cyclic mapping only after a delay that does not exceed a maximal predefined delay.

### Claim 17 (depends on 11)

The method according to claim 11, wherein modifying the cyclic mapping comprises swapping a time slot assigned in the cyclic mapping to an output port to which the given buffer is routed, with a different time slot assigned in the cyclic mapping to another output port in the selected group.

### Claim 18 (depends on 17)

The method according to claim 17, wherein the different time slot is assigned for transmission by another buffer, and comprising verifying that a required rate of readout from the another buffer is less than a maximum rate supported by the another buffer.

### Claim 19 (depends on 11)

The method according to claim 11, wherein applying the routing plan comprises coordinating, for each time slot, between (i) reading from a buffer using a specified read interface, (ii) applying a specified routing scheme within the crossbar fabric, and (iii) outputting the read data to a specified output port.

### Claim 20 (depends on 11)

The method according to claim 11, and comprising, in response to identifying that a transmission queue associated with a given output port is congested, giving the group of output ports to which the given output port belongs, high priority to be selected for cyclic mapping modification.
