# US 2017/0289048 A1 · Methods and apparatus for alleviating congestion at a switch, such as a shallow buffered switch

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

- Number: US 2017/0289048 A1
- Document ID: US20170289048A1
- Status: Published application
- Kind: A1
- Application number: 15/474,445
- Filed: 2017-03-30
- Published: 2017-10-05
- Earliest claimed: 2016-03-30
- Assignees: New York University
- Applicants: New York University
- Inventors: H. Jonathan CHAO; Kuan-yin CHEN; Yang XU
- Web page: https://patentgrep.com/patent/US20170289048A1

## CPC

- H04L 47/30: in combination with information about buffer occupancy at either end or at transit nodes
- H04L 43/0864: Round trip delays
- H04L 43/14: {using software, i.e. software packages (network security related monitoring H04L63/1408)}
- H04L 49/505: Corrective measures
- H04L 43/16: Threshold monitoring
- H04L 47/11: Identifying congestion
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The problem of collisions and/or congestion at output ports of switches, especially in shallow-buffered commodity switches, can be solved by: (a) receiving by the switch, a packet; (b) extracting destination information from the packet; (c) looking up, using the extracted destination information, an output port for the packet; (d) determining whether or not to redirect the packet based on a congestion level of a buffer associated with the output port; (f) responsive to a determination to redirect the packet, (1) dispatching the packet to a dedicated reservoir port of the switch, wherein the reservoir port enforces a queue discipline, (2) receiving, by a reservoir, the redirected packet, (3) temporarily buffering, in an internal queue of the reservoir, the received, redirected packet, and (4) sending the temporarily buffered, received, redirected packet back to the switch. Otherwise, responsive to a determination to not redirect the packet, the packet is dispatched to the output port of the switch. In at least some example embodiments consistent with the present invention, any packets sent back to the switch are paced such that collisions and congestion at the switch output port is relieved.

## Claims

### Claim 1

A computer-implemented method for handling network traffic surges at a shallow-buffered switch, the computer-implemented method comprising:
a) receiving by the switch, a packet;
b) extracting destination information from the packet;
c) looking up, using the extracted destination information, an output port for the packet;
d) determining whether or not to redirect the packet based on a congestion level of a buffer associated with the output port;
f) responsive to a determination to redirect the packet,
1) dispatching the packet to a dedicated reservoir port of the switch, wherein the reservoir port enforces a queue discipline,
2) receiving, by a reservoir, the redirected packet,
3) temporarily buffering, in an internal queue of the reservoir, the received, redirected packet, and
4) sending the temporarily buffered, received, redirected packet back to the switch, and
otherwise, responsive to a determination to not redirect the packet, dispatching the packet to the output port of the switch.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1 wherein any packets sent back to the switch are paced such that collisions and congestion at the switch output port is relieved.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2 wherein any packets sent back to the switch are paced such that collisions and congestion at the switch output port is relieved by (1) providing a leaky bucket (LB) at an exit of the internal queue of the reservoir, and (2) adaptively setting a drain rate of the leaky bucket.

### Claim 4 (depends on 3)

The computer-implemented method of claim 3 wherein the drain rate of the leaky bucket is adaptively set based on a congestion status of the switch inferred from information directly available at the reservoir.

### Claim 5 (depends on 4)

The computer-implemented method of claim 4 wherein the congestion status of the switch is inferred by
1) repeatedly monitoring a number of packets received by the reservoir,
2) repeatedly calculating a rate of data detouring to the reservoir based on the monitored number of packets received by the reservoir, and
3) inferring that the congestion status of the switch is “congested” responsive to a determination that the calculated rate of data is greater than a preset threshold, and otherwise, inferring that the congestion status of the switch is “not congested” responsive to a determination that the calculated rate of data is not greater than the preset threshold.

### Claim 6 (depends on 4)

The computer-implemented method of claim 4 wherein the congestion status of the switch is inferred by
1) periodically sending out, from the reservoir, with highest priority, a probe packet to the dedicated reservoir port of the of the switch, wherein the probe packet contains a timestamp marking its exit time from the reservoir,
2) recording the timestamp of the sent probe packet,
3) receiving by the reservoir, back from the switch, the previously sent probe packet,
4) calculating a total time delay experienced by the probe packet using the recorded time stamp and a time the probe packet was received back from the switch by the reservoir, and
5) inferring a switch congestion value from the total time delay.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1 wherein any packets sent back to the switch from the reservoir are forwarded to the intended output port with a highest priority.

### Claim 8 (depends on 1)

The computer-implemented method of claim 1 wherein any packets sent back to the switch from the reservoir are not checked for further redirection more than a predetermined number of times (n) such that no packet can traverse the reservoir more than n-1 times.

### Claim 9 (depends on 1)

The computer-implemented method of claim 1 wherein the act of determining whether or not to redirect the packet based on a congestion level of a buffer associated with the output port includes
1) determining whether or not the buffer associated with the output port is full, and
2) determining to redirect the packet responsive to a determination that the buffer associated with the output port is full, and otherwise, determining to not redirect the packet responsive to a determination that the buffer associated with the output port is not full.

### Claim 10 (depends on 1)

The computer-implemented method of claim 1 wherein the act of determining whether or not to redirect the packet based on a congestion level of a buffer associated with the output port includes
1) querying an active queue management (AQM) module of the output port for a drop/mark determination;
2) responsive to receiving a drop/mark determination from the AQM module, determining to redirect the packet instead of dropping the packet, and otherwise, responsive to receiving a determination from the AQM module to not drop/mark, not determining to redirect the packet.

### Claim 11

A computer-implemented method for handling network traffic surges at a shallow-buffered switch, the computer-implemented method comprising:
a) receiving by the switch, a packet;
b) extracting a destination information from the packet;
c) performing an IP lookup, using the extracted destination information, to determine an output port of the switch;
d) querying an active queue management (AQM) module of the output port for a redirection probability between 0 and 1;
e) receiving from the AQM module a redirection probability between 0 and 1;
f) generating a uniform random floating point number for the packet;
g) determining to redirect the packet when r≦q, where r is the random number and q is the retrieved redirection probability, and otherwise, not determining to redirect the packet; and
h) responsive to a determination to redirect the packet, forwarding the packet to a dedicated reservoir port of the switch to effect a redirection of the packet to a reservoir, and otherwise, responsive to a determination to not redirect the packet, not forwarding the packet to the reservoir.

### Claim 12

A computer-implemented method for handling network traffic surges at a shallow-buffered switch, the computer-implemented method comprising:
a) receiving by the switch, a packet;
b) extracting a destination information from the packet;
c) performing an IP lookup, using the extracted destination information, to determine an output port of the switch;
d) querying an active queue management (AQM) module of the output port for a redirection probability between 0 and 1;
e) receiving from the AQM module a redirection probability between 0 and 1;
f) extracting from the packet, transport layer flow information;
g) mapping, using a hash function, the extracted transport layer flow information to a pseudo-random number within a hash range of the hash function;
h) calculating a redirection region with the hash range based on the received redirection probability;
i) determining to redirect the packet responsive to a determination that the pseudo-random number corresponding the received packet is within the redirection region, and otherwise, responsive to a determination that the pseudo-random number corresponding to the received packet is not within the redirection region, not determining to redirect the packet; and
j) responsive to a determination to redirect the packet, forwarding the packet to a dedicated reservoir port of the switch to effect a redirection of the packet to a reservoir, and otherwise, responsive to a determination to not redirect the packet, not forwarding the packet to the reservoir.

### Claim 13

A computer-implemented method for relieving network traffic surges at an external shallow-buffered switch, the computer-implemented method comprising:
a) receiving, by a reservoir, a redirected packet dispatched from a reservoir port of the switch;
b) temporarily buffering, in an internal queue of the reservoir, the received, redirected packet, and
c) sending the temporarily buffered, received, redirected packet back to the external switch in a paced manner such that collisions and congestion at an output port of the external switch is relieved.

### Claim 14 (depends on 13)

The computer-implemented method of claim 13 wherein the redirected packet is sent back to the switch in a paced manner such that collisions and congestion at the switch output port is relieved by (1) providing a leaky bucket (LB) at an exit of the internal queue of the reservoir, and (2) adaptively setting a drain rate of the leaky bucket.

### Claim 15 (depends on 14)

The computer-implemented method of claim 14 wherein the drain rate of the leaky bucket is adaptively set based on a congestion status of the external switch inferred from information directly available at the reservoir.

### Claim 16 (depends on 15)

The computer-implemented method of claim 15 wherein the congestion status of the external switch is inferred by
1) repeatedly monitoring a number of packets received by the reservoir,
2) repeatedly calculating a rate of data detouring to the reservoir based on the monitored number of packets received by the reservoir, and
3) inferring that the congestion status of the external switch is “congested” responsive to a determination that the calculated rate of data is greater than a preset threshold, and otherwise, inferring that the congestion status of the external switch is “not congested” responsive to a determination that the calculated rate of data is not greater than the preset threshold.

### Claim 17 (depends on 15)

The computer-implemented method of claim 15 wherein the congestion status of the external switch is inferred by
1) periodically sending out, from the reservoir, with highest priority, a probe packet to the dedicated reservoir port of the of the external switch, wherein the probe packet contains a timestamp marking its exit time from the reservoir,
2) recording the timestamp of the sent probe packet,
3) receiving by the reservoir, back from the external switch, the previously sent probe packet,
4) calculating a total time delay experienced by the probe packet using the recorded time stamp and a time the probe packet was received back from the external switch by the reservoir, and
5) inferring a switch congestion value from the total time delay.

### Claim 18

A reservoir for relieving network traffic surges at an external shallow-buffered switch, reservoir comprising:
a) an input port for receiving a redirected packet dispatched from a reservoir port of the external switch;
b) an internal queue temporarily buffering the received, redirected packet, and
c) a scheduler for sending the temporarily buffered, received, redirected packet back to the external switch in a paced manner such that collisions and congestion at an output port of the external switch is relieved.

### Claim 19 (depends on 18)

The reservoir of claim 18 wherein the scheduler includes a leaky bucket (LB) at an exit of the internal queue of the reservoir and wherein the scheduler sends the redirected packet back to the switch in a paced manner such that collisions and congestion at the switch output port is relieved adaptively setting a drain rate of the leaky bucket.

### Claim 20 (depends on 19)

The reservoir of claim 19 wherein the drain rate of the leaky bucket is adaptively set based on a congestion status of the external switch inferred from information directly available at the reservoir.

### Claim 21 (depends on 20)

The reservoir of claim 20 further comprising:
d) a controller, wherein the controller infers the congestion status of the external switch by
1) repeatedly monitoring a number of packets received by the reservoir,
2) repeatedly calculating a rate of data detouring to the reservoir based on the monitored number of packets received by the reservoir, and
3) inferring that the congestion status of the external switch is “congested” responsive to a determination that the calculated rate of data is greater than a preset threshold, and otherwise, inferring that the congestion status of the external switch is “not congested” responsive to a determination that the calculated rate of data is not greater than the preset threshold.

### Claim 22 (depends on 20)

The reservoir of claim 20 further comprising:
d) a controller, wherein the controller infers the congestion status of the external switch by
1) periodically sending out, from the reservoir, with highest priority, a probe packet to the dedicated reservoir port of the of the external switch, wherein the probe packet contains a timestamp marking its exit time from the reservoir,
2) recording the timestamp of the sent probe packet,
3) receiving by the reservoir, back from the external switch, the previously sent probe packet,
4) calculating a total time delay experienced by the probe packet using the recorded time stamp and a time the probe packet was received back from the external switch by the reservoir, and
5) inferring a switch congestion value from the total time delay.

### Claim 23

A reservoir for relieving network traffic surges at an external shallow-buffered switch having a plurality of output ports and at least one reservoir port, reservoir comprising:
a) at least one input port for receiving redirected packets dispatched from the at least one reservoir port of the external switch;
b) at least one output port for sending redirected packets back to the external switch;
c) a plurality of internal queues, each of the plurality of internal queues
1) corresponding to one of the plurality of output ports of the external switch, and
2) temporarily buffering those of the received redirected packets from the external switch that were destined for the corresponding output port of the external switch, and
d) a scheduler including
1) a plurality of cushion buffers, each of the cushion buffers
A) corresponding to one of the plurality of internal queues, and
B) having a capacity that is smaller than its corresponding internal queue,
2) a plurality of first arbiters, each of the first arbiters
A) corresponding to one of the plurality of internal queues, and
B) configured for deciding when to send packets from its corresponding queue to the corresponding cushion buffer in a paced manner such that collisions and congestion at an output port of the external switch is relieved, the scheduler, and
3) a second arbiter adapted to schedule forwarding of redirected packets from the plurality of cushion buffers to the at least one output port.

### Claim 24 (depends on 23)

The reservoir of claim 23 wherein each of the plurality of internal queues is divided into one of (A) per-flow, (B) per-class, or (C) per-priority queues.

### Claim 25 (depends on 23)

The reservoir of claim 23 wherein each of the first arbiters includes a leaky bucket (LB) at an exit of its corresponding internal queue, and wherein a drain rate of the leaky bucket is adaptively set based on a congestion status of the external switch at the corresponding output port inferred from information directly available at the reservoir.

### Claim 26 (depends on 23)

The reservoir of claim 23 wherein the second arbiter is a round-robin arbiter.
