Dynamic Synchronized Scheduling in a Computer Network

• US 20120155260A1
• Filed: 12/17/2010
• Published: 06/21/2012
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Shaffer, Shmuel, Okwudiafor, Charles, Shetty, Sandeep Jay
• Granted Patent: US 8,830,837 B2
• Time in Patent Office: Days
• US Class Current: 370/230.1
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

In one embodiment, a receiving node in a computer network may detect congestion, and also identifies a set (e.g., subset) of its neighbor nodes. In response to the congestion, the receiving node may assign a transmission timeslot to each neighbor node of the set based on the congestion, where each neighbor is allowed to transmit (synchronously) only during its respective timeslot. The assigned timeslots may then be transmitted to the set of neighbor nodes. In another embodiment, a transmitting node (e.g., a neighbor node of the receiving node) may receive a scheduling packet from the receiving node. Accordingly, the transmitting node may determine its assigned transmission timeslot during which the transmitting node is allowed to transmit. As such, the transmitting node may then transmit packets only during the assigned timeslot (e.g., for a given time). In this manner, congestion at the receiving node may be reduced.

Claims

1. A method, comprising:

detecting indicia of congestion at a receiving node in a computer network;

identifying a set of neighbor nodes to the receiving node;

assigning at least one transmission timeslot to each neighbor node of the set, with the transmission timeslot of at least one neighbor node being assigned based on the detected indicia of congestion, each neighbor being allowed to transmit synchronously with other neighbor nodes of the set only during its respective timeslot; and

transmitting the assigned timeslots to the set of neighbor nodes.

2. The method as in claim 1, wherein identifying the set comprises:

determining a subset of all neighbor nodes of the receiving node.

3. The method as in claim 2, wherein determining comprises:

determining a congestion contribution by each neighbor node; and

selecting the subset based on the congestion contribution of each neighbor node.

4. The method as in claim 1, wherein identifying the set is performed in response to detecting the indicia of congestion.

5. The method as in claim 1, wherein assigning the timeslots comprises:

assigning timeslots as a round-robin assignment to the set of neighbor nodes.

6. The method as in claim 1, wherein assigning the timeslots comprises:

assigning variable timeslots to each neighbor of the set of neighbor nodes based on the detected indicia of congestion.

7. The method as in claim 1, wherein assigning the timeslots comprises:

assigning a different number of timeslots within a sequence of timeslots to one or more particular neighbors of the set of neighbor nodes based on the detected indicia of congestion.

8. The method as in claim 1, wherein transmitting comprises:

utilizing a link local multicast packet.

9. The method as in claim 1, further comprising:

setting a length of time for which the assigned timeslots are to be used.

10. The method as in claim 9, further comprising:

in response to expiration of the length of time, transmitting a schedule clearing packet to instruct the neighbor nodes to no longer use the assigned timeslots.

11. The method as in claim 9, further comprising:

increasing the length of time for subsequent detected indicia of congestion.

12. The method as in claim 1, wherein detecting comprises:

expecting indicia of congestion at the receiving node; and

assigning timeslots and transmitting the timeslots to the neighbors in response to the expected indicia of congestion.

13. The method as in claim 1, further comprising:

receiving notification from a particular neighbor node that the particular neighbor node does not need its particular assigned timeslot; and

in response, allowing the particular assigned timeslot to be assigned to other neighbor nodes of the set.

14. The method as in claim 1, further comprising:

measuring an indicia of congestion relating to a particular one of the transmitting nodes;

accessing a threshold relating to the indicia of congestion;

comparing the accessed threshold to the measured indicia of congestion relating to the particular one of the transmitting nodes;

responsive to a determination that the accessed threshold is met by the measured indicia of congestion relating to the particular one of the transmitting nodes, assigning a disproportionate aggregate transmission timeslot to the particular one of the transmitting nodes relative to other of the transmitting nodes.

15. An apparatus, comprising:

one or more network interfaces to communicate in a computer network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

detect indicia of congestion at a receiving node in a computer network;

identify a set of neighbor nodes to the receiving node;

assign at least one transmission timeslot to each neighbor node of the set, with the transmission timeslot of at least one neighbor node being assigned based on the detected indicia of congestion, each neighbor being allowed to transmit synchronously with other neighbor nodes of the set only during its respective timeslot; and

transmit the assigned timeslots to the set of neighbor nodes

16. The apparatus as in claim 15, wherein the process when executed to identify the set is operable to:

determine a subset of all neighbor nodes of the apparatus.

17. The apparatus as in claim 15, wherein the process when executed to assign the timeslots is operable to perform at least one of the following:

assign timeslots as a round-robin assignment to the set of neighbor nodes;

assign variable timeslots to each neighbor of the set of neighbor nodes based on the detected indicia of congestion; and

assign a different number of timeslots within a sequence of timeslots to one or more particular neighbors of the set of neighbor nodes based on the detected indicia of congestion.

18. The apparatus as in claim 15, wherein the process when executed is further operable to:

set a length of time for which the assigned timeslots are to be used.

19. A method, comprising:

receiving, at a transmitting node, a scheduling packet from a receiving node to which packets are transmitted from the transmitting node;

determining a transmission timeslot assigned to the transmitting node, the transmitting node being allowed to transmit synchronously with other neighbor nodes of the receiving node only during its respective timeslot; and

, in response,

transmitting packets from the transmitting node only during the assigned timeslot.

20. The method as in claim 19, further comprising:

determining a length of time for which the assigned timeslots are to be used; and

in response to expiration of the length of time, transmitting non-synchronized packets from the transmitting node.

21. The method as in claim 19, further comprising:

receiving a schedule clearing packet to instruct the transmitting node to no longer use the assigned timeslots; and

, in response,

transmitting non-synchronized packets from the transmitting node.

22. The method as in claim 19, further comprising:

determining that the transmitting node does not need its assigned timeslot; and

in response, notifying the receiving node that the particular timeslot is allowed to be assigned to other neighbor nodes of the receiving node.

23. An apparatus, comprising:

one or more network interfaces to communicate in a computer network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

receive a scheduling packet from a receiving node to which packets are transmitted from the apparatus;

determine a transmission timeslot assigned to the apparatus, the apparatus being allowed to transmit synchronously with other neighbor nodes of the receiving node only during its respective timeslot; and

transmit packets only during the assigned timeslot.

24. The apparatus as in claim 23, wherein the process when executed set is further operable to:

determine a length of time for which the assigned timeslots are to be used; and

transmit non-synchronized packets in response to expiration of the length of time.

25. The apparatus as in claim 23, wherein the process when executed set is further operable to:

receive a schedule clearing packet to instruct the apparatus to no longer use the assigned timeslots; and

transmit non-synchronized packets in response to the schedule clearing packet.