Adjusting communication capacity in a multi-stage routing network

Patent metadata

Field	Value
Publication number	US-9807645-B1
Application number	US-201514748916-A
Country	US
Kind code	B1
Filing date	Jun 24, 2015
Priority date	Jun 24, 2015
Publication date	Oct 31, 2017
Grant date	Oct 31, 2017

Abstract

A method for adjusting capacity in a multi-stage routing network includes monitoring a number of available connections between a router in a first stage of a multi-stage router network and one or more routers in a second stage of the multi-stage router network. Each of the stages of the multi-stage router network may include a plurality of routers. The method may also include detecting that the number of available connections falls below a threshold number. A notification can be sent to one or more routers in a third stage of the multi-stage router network that the router in the first stage is deprioritized. The one or more routers in the third stage can be operated so that communications to the first stage are routed to one or more other routers in the first stage.

First claim

What is claimed is:

1. A method for adjusting capacity in a multi-stage routing network, the method comprising:
monitoring a number of available connections between a first router in a first stage of the multi-stage router network having a first threshold number, a second router in the first stage of the multi-stage network having a second threshold number, and one or more routers in a second stage of the multi-stage router network, wherein each of the stages of the multi-stage router network includes a plurality of routers;
detecting that the number of available connections for the first router falls below the first threshold number;
detecting that the number of available connections for the second router falls below the second threshold number;
sending a notification to one or more routers in a third stage of the multi-stage router network based on the number of available connections for the first router falling below the first threshold number and the number of available connections for the second router falling below the second threshold number that the routers in the first stage are deprioritized; and
operating the one or more routers in the third stage so that communications to the first stage are routed to one or more other routers in the first stage.

2. The method according to claim 1 , further comprising:
detecting that the number of available connections between the first router in the first stage and the one or more routers in the second stage is equal to or greater than the first threshold number.

3. The method according to claim 2 , further comprising:
upon detecting that the number of available connections between the first router in the first stage is equal to or greater than the first threshold number, sending a notification to the one or more routers in the third stage that the first router in the first stage is priority normalized.

4. The method according to claim 1 , wherein the first threshold number is associated with the first stage, the method further comprising:
obtaining the first threshold number from a policy document of the multi-stage routing network.

5. The method according to claim 1 , further comprising:
communicating a test message to the plurality of routers in the second stage to determine the number of available connections.

6. The method according to claim 1 , wherein the multi-stage routing network comprises a core stage, an aggregation stage, and an access stage.

7. The method according to claim 1 , wherein the first threshold number and the second threshold number are not equal.

8. A non-transitory computer-readable storage medium including instructions that, upon execution, cause a computer system to:
detect that a number of active connections between a first router in a first stage of a multi-stage router network is below a first threshold number;
detect that a number of active connections between a second router in the first stage of a multi-stage router network is below a second threshold number;
detect that one or more routers in an adjacent second stage of the multi-stage router network is below the first threshold number; and
send a notification based on the number of active connections for the first router falling below the first threshold number and the number of active connections for the second router falling below the second threshold that the first and second routers are unavailable so that communications to the first stage are routed to one or more other routers in the first stage.

9. The computer-readable storage medium according to claim 8 , wherein the instructions, upon execution, further cause the computer system to:
send the notification to one or more routers in an adjacent third stage of the multi-stage router network that the first router is deprioritized.

10. The computer-readable storage medium according to claim 9 , wherein the instructions, upon execution, further cause the computer system to:
upon detecting the number of active connections is equal to or greater than the first threshold number, send a notification to the one or more routers in the adjacent third stage that the router is priority normalized.

11. The computer-readable storage medium according to claim 8 , wherein the instructions, upon execution, further cause the computer system to set priority of the first router such that no traffic is communicated to the router.

12. The computer-readable storage medium according to claim 8 , wherein the instructions, upon execution, further cause the computer system to:
communicate a test message to the one or more routers in the adjacent second stage.

13. The computer-readable storage medium according to claim 12 , wherein the instructions, upon execution, further cause the computer system to:
determine the number of active connections based on a number of responses to the test message received at the router.

14. The computer-readable storage medium according to claim 8 , wherein the instructions, upon execution, further cause the computer system to:
monitor the number of active connections between the first router in the first stage and the one or more routers in the adjacent second stage.

15. The computer-readable storage medium according to claim 8 , wherein the multi-stage router network comprises a Clos network.

16. The computer-readable storage medium according to claim 8 , wherein the multi-stage router network comprises a core stage, an aggregation stage, and an access stage.

17. The computer-readable storage medium according to claim 8 , wherein the instructions, upon execution, further cause the computer system to:
monitor a number of available connections between the first router in the first stage and one or more routers in at least two stages adjacent to the first stage;
send a notification that the first router is unavailable, when the number of available connections between the first router in the first stage and the one or more routers in one of the at least two stages falls below the first threshold number.

18. The computer readable storage medium according to claim 8 , wherein the first threshold number and the second threshold number are not equal.

19. A system, comprising:
a plurality of routers in a multi-stage router network, the plurality of routers arranged in at least a first stage, a second stage and a third stage of the multi-stage router network; and
a router monitoring service communicatively coupled to the plurality of routers, the router monitoring service operable to:
monitor a number of available connections between a first router in the first stage of the multi-stage router network, a second router in the first stage of the multi-stage router network, and one or more of the plurality of routers in the second stage of the multi-stage router network;

detect that the number of available connections to the first router falls below a first threshold number;
detect that the number of available connections to the second router falls below a second threshold number;
send a notification to one or more of the plurality of routers in the third stage of the multi-stage router network based on the number of available connections for the first router falling below the first threshold number and the number of available connections for the second router falling below the second threshold number that the first and second routers in the first stage are deprioritized; and
operate the one or more routers in the third stage so that communications to the first stage are routed to one or more other routers in the first s

Assignees

• Amazon Tech Inc

Inventors

• Callaghan Stephen
• Tracy Leonard Thomas
• Kelly Mark Noel
• Judge Alan Michael
• Pietsch Justin Oliver
• Sahoo Amit

Classifications

• H04W28/0289 Primary

  Congestion control (load shedding arrangements in network planning H04W16/08; performing reselection for handling the traffic H04W36/22; wireless traffic scheduling H04W72/12) · CPC title

• H04W40/005

  Routing actions in the presence of nodes in sleep or doze mode · CPC title

• H04L45/125 Primary

  based on throughput or bandwidth · CPC title

• H04L45/60

  Router architectures · CPC title

• H04L45/583

  Stackable routers · CPC title