Method and system for reserving bandwidth in time-division multiplexed networks

• US 8,160,096 B1
• Filed: 12/06/2006
• Issued: 04/17/2012
• Est. Priority Date: 12/06/2006
• Status: Active Grant

• Current Assignee: Tadaaki Chigusa
• Original Assignee: Tadaaki Chigusa
• Inventors: Anburaj, Michael
• Primary Examiner(s): Phung, Luat
• Application Number:
  US11/636,063
• Time in Patent Office: 1,959 Days
• Field of Search: 370/468, 370/254, 370/255, 370/329, 370/345, 370/346, 370/348, 375/400
• US Class Current: 370/468
• CPC Class Codes: H04J 3/1605 Fixed allocated frame structures

Abstract

Methods and systems for reserving bandwidth in communications networks (e.g., time-division multiplexed (TDM) networks). A bandwidth request on a forward path of the communications network is temporarily held without any fixed slot timings. The bandwidth request is held for a time long enough for the request to travel the forward path end-to-end. Once the request reaches the destination of the forward path, the temporary bandwidth is confirmed by sending a bandwidth confirmation message back from destination to the source of the path. Each slave node along the path performs an allocation confirm with its associated master node, which responds by converting the temporary holds to full allocations by fixing slot timings.

Claims

1. A method of reserving bandwidth along an end-to-end path formed between a source node and a destination node in a network comprising a plurality of nodes, the method comprising:

allocating a first time slot in a node for a first communications link in a first end-to-end path;

receiving, at the node and after allocating the first time slot, a bandwidth request for a second communications link in a second end-to-end path;

temporarily holding bandwidth in the node as a floating hold for the second end-to-end path, without allocating a resulting time slot, in response to the bandwidth request for the second communications link;

receiving, at the node and after receiving the bandwidth request for the second communications link, a bandwidth request for a third communications link on a third end-to-end path;

temporarily holding bandwidth in the node as a floating hold for the third end-to-end path, without allocating a resulting time slot, in response to the bandwidth request for the third communications link;

determining sufficient bandwidth resources are available to accommodate the bandwidth request for the third communications link; and

allocating the temporarily held bandwidth for the third end-to-end path to a second time slot directly adjacent to the first time slot while still holding the temporarily held bandwidth for the second end-to-end path based on the determining sufficient bandwidth resources are available to accommodate the bandwidth request for the third communications link.

2. The method of claim 1, further comprising:

determining sufficient bandwidth resources are available to accommodate the bandwidth request for the second communications link; and

allocating the temporarily held bandwidth for the second end-to-end path to a third time slot directly adjacent to the second time slot based on the determining sufficient bandwidth resources are available to accommodate the bandwidth request for the second communications link.

3. The method of claim 1, further comprising:

receiving, at the node and after receiving the bandwidth request for the third communications link, a bandwidth request for a fourth communications link on a fourth end-to-end path;

temporarily holding bandwidth in the node as a floating hold for the fourth end-to-end path, without allocating a resulting time slot, in response to the bandwidth request for the fourth communications link;

determining sufficient bandwidth resources are available to accommodate the bandwidth request for the fourth communications link; and

allocating the temporarily held bandwidth for the fourth end-to-end path to a third time slot directly adjacent to the second time slot while still holding the temporarily held bandwidth for the second end-to-end path based on the determining sufficient bandwidth resources are available to accommodate the bandwidth request for the fourth communications link.

4. The method of claim 1, further comprising releasing the temporarily held bandwidth for the second end-to-end path.

5. The method of claim 1, further comprising:

determining insufficient bandwidth resources are available to satisfy the bandwidth request for the second communications link in the second end-to-end path; and

releasing the temporarily held bandwidth for the second end-to-end path based on the determining insufficient bandwidth resources are available to satisfy the bandwidth request for the second communications link in the second end-to-end path.

6. The method of claim 1, further comprising:

allocating a first time slot in a second node for the first communications link in the first end-to-end path;

receiving, at the second node and after allocating the first time slot in the second node, a bandwidth request for a fourth communications link in a fourth end-to-end path;

temporarily holding bandwidth in the second node as a floating hold for the fourth end-to-end path, without allocating a resulting time slot, in response to the bandwidth request for the fourth communications link;

receiving, at the second node and after receiving the bandwidth request for the fourth communications link, a bandwidth request for a fifth communications link on a fifth end-to-end path;

temporarily holding bandwidth in the second node as a floating hold for the fifth end-to-end path, without allocating a resulting time slot, in response to the bandwidth request for the fifth communications link;

determining sufficient bandwidth resources are available to accommodate the bandwidth request for the fifth communications link; and

allocating the temporarily held bandwidth for the fifth end-to-end path to a second time slot of the second node directly adjacent to the first time slot of the second node while still holding the temporarily held bandwidth for the fourth end-to-end path based on the determining sufficient bandwidth resources are available to accommodate the bandwidth request for the fifth communications link.

7. The method of claim 1, wherein the first communications link comprises a wireless communications link.

8. The method of claim 1, wherein the first communications link comprises a wired communications link.

9. The method of claim 1, wherein the first end-to-end path comprises a multi-hop path in a mesh network.

10. The method of claim 1, further comprising:

allocating bandwidth for a fourth end-to-end path to a third time slot directly adjacent to the second time slot;

releasing the second time slot of the third end-to-end path; and

reallocating the bandwidth for the fourth end-to-end path from the third time slot to the second time slot and releasing the third time slot.

11. The method of claim 1, further comprising:

receiving a bandwidth adjustment request;

sending a bandwidth adjustment announcement to a second node, in response to receiving the bandwidth adjustment request;

receiving, from the second node, a bandwidth request acknowledgment; and

instructing the second node to adjust slot timings for a previously allocated bandwidth in response to receiving the bandwidth request acknowledgment.

12. The method of claim 11, further comprising:

wherein receiving the bandwidth adjustment request adjustment comprises receiving the bandwidth adjustment request from a third node;

wherein instructing the second node to adjust slot timings comprises instructing the second node to adjust slot timings at a time of instructing the third node to adjust slot timings.

13. The method of claim 12, wherein the second node and the third node are in a common end-to-end path.

14. The method of claim 1, wherein the first time slot and the second time slot comprise different time widths.

15. A node for reserving bandwidth along an end-to-end path formed between a source node and a destination node in a network comprising a plurality of nodes, the node using a first time slot and a second time slot and the node configured to:

allocate the first time slot in the node for a first communications link in a first end-to-end path;

receive, at the node and after allocating the first time slot, a bandwidth request for a second communications link in a second end-to-end path;

temporarily hold bandwidth in the node as a floating hold for the second end-to-end path, without allocating a resulting time slot, in response to the bandwidth request for the second communications link;

receive, at the node and after receiving the bandwidth request for the second communications link, a bandwidth request for a third communications link on a third end-to-end path;

temporarily hold bandwidth in the node as a floating hold for the third end-to-end path, without allocating a resulting time slot, in response to the bandwidth request for the third communications link;

determine sufficient bandwidth resources are available to accommodate the bandwidth request for the third communications link; and

allocate the temporarily held bandwidth for the third end-to-end path to the second time slot directly adjacent to the first time slot while still holding the temporarily held bandwidth for the second end-to-end path based on determining sufficient bandwidth resources are available to accommodate the bandwidth request for the third communications link.

16. The node of claim 15, the code further configured to:

determine sufficient bandwidth resources are available to accommodate the bandwidth request for the second communications link; and

allocate the temporarily held bandwidth for the second end-to-end path to a third time slot directly adjacent to the second time slot based on determining sufficient bandwidth resources are available to accommodate the bandwidth request for the second communications link.

17. The node of claim 15, the code further configured to:

receive, at the node and after receiving the bandwidth request for the third communications link, a bandwidth request for a fourth communications link on a fourth end-to-end path;

temporarily hold bandwidth in the node as a floating hold for the fourth end-to-end path, without allocating a resulting time slot, in response to the bandwidth request for the fourth communications link;

determine sufficient bandwidth resources are available to accommodate the bandwidth request for the fourth communications link; and

allocate the temporarily held bandwidth for the fourth end-to-end path to a third time slot directly adjacent to the second time slot while still holding the temporarily held bandwidth for the second end-to-end path based on determining sufficient bandwidth resources are available to accommodate the bandwidth request for the fourth communications link.

18. The node of claim 15, the code further configured to:

release the temporarily held bandwidth for the second end-to-end path.

19. The node of claim 15, the code further configured to:

determine insufficient bandwidth resources are available to satisfy the bandwidth request for the second communications link in the second end-to-end path; and

release the temporarily held bandwidth for the second end-to-end path based on determining insufficient bandwidth resources are available to satisfy the bandwidth request for the second communications link in the second end-to-end path.

20. The node of claim 15, wherein the first time slot and the second time slot comprise different time widths.

21. A network for reserving bandwidth along an end-to-end path formed between a source node and a destination node, the network comprising a plurality of nodes each configured to:

allocate a first time slot in a node for a first communications link in a first end-to-end path;

receive, at the node and after allocating the first time slot, a bandwidth request for a second communications link in a second end-to-end path;

temporarily hold bandwidth in the node as a floating hold for the second end-to-end path, without allocating a resulting time slot, in response to the bandwidth request for the second communications link;

receive, at the node and after receiving the bandwidth request for the second communications link, a bandwidth request for a third communications link on a third end-to-end path;

temporarily hold bandwidth in the node as a floating hold for the third end-to-end path, without allocating a resulting time slot, in response to the bandwidth request for the third communications link;

determine sufficient bandwidth resources are available to accommodate the bandwidth request for the third communications link; and

allocate the temporarily held bandwidth for the third end-to-end path to a second time slot directly adjacent to the first time slot while still holding the temporarily held bandwidth for the second end-to-end path based on determining sufficient bandwidth resources are available to accommodate the bandwidth request for the third communications link.

22. The network of claim 21, further comprising:

determine sufficient bandwidth resources are available to accommodate the bandwidth request for the second communications link; and

allocate the temporarily held bandwidth for the second end-to-end path to a third time slot directly adjacent to the second time slot based on determining sufficient bandwidth resources are available to accommodate the bandwidth request for the second communications link.

23. The network of claim 21, further comprising:

receive, at the node and after receiving the bandwidth request for the third communications link, a bandwidth request for a fourth communications link on a fourth end-to-end path;

temporarily hold bandwidth in the node as a floating hold for the fourth end-to-end path, without allocating a resulting time slot, in response to the bandwidth request for the fourth communications link;

determine sufficient bandwidth resources are available to accommodate the bandwidth request for the fourth communications link; and

allocate the temporarily held bandwidth for the fourth end-to-end path to a third time slot directly adjacent to the second time slot while still holding the temporarily held bandwidth for the second end-to-end path based on determining sufficient bandwidth resources are available to accommodate the bandwidth request for the fourth communications link.

24. The network of claim 21, further comprising:

release the temporarily held bandwidth for the second end-to-end path.

25. The network of claim 21, further comprising:

determine insufficient bandwidth resources are available to satisfy the bandwidth request for the second communications link in the second end-to-end path; and

release the temporarily held bandwidth for the second end-to-end path based on determining insufficient bandwidth resources are available to satisfy the bandwidth request for the second communications link in the second end-to-end path.

26. The network of claim 21, wherein the first communications link comprises a wireless communications link.

27. The network of claim 21, wherein the first communications link comprises a wired communications link.

28. The network of claim 21, wherein the first end-to-end path comprises a multi-hop path in a mesh network.

29. The network of claim 21, further comprising:

allocate bandwidth for a fourth end-to-end path to a third time slot directly adjacent to the second time slot;

release the second time slot of the third end-to-end path; and

reallocate the bandwidth for the fourth end-to-end path from the third time slot to the second time slot and releasing the third time slot.

30. The network of claim 21, wherein the first time slot and the second time slot comprise different time widths.