Method for reserving network resources using a hierarchical/segment tree for starting and ending times of request

• US 6,760,306 B1
• Filed: 09/27/2000
• Issued: 07/06/2004
• Est. Priority Date: 09/27/2000
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Pan, Yin, Edwards, Eric, Villarica, Al
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US09/672,114
• Time in Patent Office: 1,378 Days
• Field of Search: 370/237, 370/230, 370/238, 370/231, 370/254, 370/255, 370/256, 370/203, 370/399, 370/395.2, 370/395.21, 370/395.3, 370/395.32, 370/395.4, 370/400, 370/411, 370/409, 370/431, 370/437, 709/213, 709/220, 709/221, 709/222, 709/223, 709/224, 709/225, 709/226-9, 710/36, 710/38, 712/220-1
• US Class Current: 370/230
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/781 Centralised allocation of resources
• CPC Class Codes: H04L 47/808 User-type aware
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/826 Involving periods of time
• CPC Class Codes: H04L 47/828 Allocation of resources per group of connections, e.g. per group of users
• CPC Class Codes: H04L 47/829 Topology based

Abstract

Data over a range of values is stored using a segment tree data structure. One or more nodes are generated to cover the range of values based on a parent node in the segment tree data structure. The one or more nodes are generated by subdividing nodes of the segment tree data structure only along paths from the parent node to the one or more nodes. The data is stored in the one or more nodes.

Claims

1. A method of storing data over a range of values using a segment tree data structure, comprising:

generating one or more nodes to cover the range of values based on a parent node in the segment tree data structure, the one or more nodes being generated by subdividing nodes of the segment tree data structure only along paths from the parent node to the one or more nodes; and

storing the data in the one or more nodes.

2. The method of claim 1, wherein the data comprises data from a network service reservation and the range of values comprise a duration of the network service reservation.

3. The method of claim 2, wherein the one or more nodes each has a granularity that makes it possible to cover, without exceeding, the duration of the network service reservation.

4. The method of claim 1, wherein subdividing comprises generating child nodes for each subdivided node, each of the child nodes covering a portion of a duration of the subdivided node.

5. The method of claim 4, wherein subdividing generates two nodes for each subdivided node, each of the two nodes covering half of the duration of the subdivided node.

6. The method of claim 1, wherein the range of values defines a time duration and the one or more nodes correspond to the time duration.

7. The method of claim 6, wherein, if more than one node is generated, resulting nodes when combined have a duration that corresponds to the time duration.

8. The method of claim 1, wherein subdividing is not performed along potential branches of the segment tree data structure that are not on paths from the parent node to the one or more nodes.

9. A method of populating nodes in segment tree data structures, comprising:

generating a first segment tree data structure that includes nodes covering a first time duration;

generating a second segment tree data structure that includes nodes covering a second time duration; and

resetting nodes in the first segment tree data structure to cover a third time duration following expiration of the first time duration.

10. The method of claim 9, further comprising:

resetting nodes in the second segment tree data structure to cover a fourth time duration following expiration of the second time duration.

11. The method of claim 9, further comprising:

receiving a network service reservation, the network service having a predetermined time duration;

determining which of the first and second segment tree data structure(s) has one or more nodes that cover the predetermined time duration; and

storing data from the network service reservation using the segment tree data structures(s) determined to have one or more nodes that cover the predetermined time duration.

12. A method of generating a segment tree data structure, comprising:

generating a parent node for an existing node of a segment tree data structure, the parent node having a duration that encompasses a duration of the existing node; and

deleting the existing node following a duration of the existing node.

13. The method of claim 12, further comprising:

deleting a descendent node of the existing node when a duration of the descendent node expires.

14. The method of claim 12, further comprising:

inserting a node beneath the parent node that covers a duration following the duration of the existing node.

15. The method of claim 14, wherein the node inserted beneath the parent node branches off to a corresponding segment tree data structure.

16. The method of claim 12, further comprising:

receiving a network service reservation, the network service reservation having a predetermined time duration;

generating one or more nodes to cover the network service reservation based on the parent node, the one or more nodes being generated by subdividing nodes of the segment tree data structure along paths from the parent node to the one or more nodes; and

storing data from the network service reservation in the one or more nodes.

17. A computer-readable medium storing a data structure, the data structure comprising:

a plurality of nodes arranged in a tree structure, the plurality of nodes comprising;

a parent node relating to a range of values; and

one or more final nodes, each of the one or more final nodes relating to a subset of the range of values;

wherein the data structure stores a predetermined range of values in the one or more final nodes; and

wherein the one or more final nodes are generated by subdividing nodes in the tree structure, starting with the parent node, along paths from the parent node to one or more nodes that correspond to the predetermined range of values.

18. The computer-readable medium of claim 17, wherein the predetermined range of values comprises data from a network service reservation.

19. The computer-readable medium of claim 17, wherein the one or more final nodes are generated by subdividing nodes in the tree structure, starting with the parent node, only along paths from the parent node to one or more nodes that correspond to the predetermined range of values.

20. A computer program stored on a computer-readable medium for storing data over a range of values using a segment tree data structure, the computer program comprising instructions that cause a computer to:

generate one or more nodes to cover the range of values based on a parent node in the segment tree data structure, the one or more nodes being generated by subdividing nodes of the segment tree data structure only along paths from the parent node to the one or more nodes; and

store the data in the one or more nodes.

21. The computer program of claim 20, wherein the data comprises data from a network service reservation and the range of values comprises a duration of the network service reservation.

22. The computer program of claim 21, wherein the one or more nodes each has a granularity that makes it possible to cover, without exceeding, the duration of the network service reservation.

23. The computer program of claim 20, wherein subdividing comprises generating child nodes for each subdivided node, each of the child nodes covering a portion of a duration of the subdivided node.

24. The computer program of claim 23, wherein subdividing generates two nodes for each subdivided node, each of the two nodes covering half of the duration of the subdivided node.

25. The computer program of claim 20, wherein the range of values defines a time duration and the one or more nodes correspond to the time duration.

26. The computer program of claim 25, wherein, if more than one node is generated, resulting nodes when combined have a duration that corresponds to the time duration.

27. The computer program of claim 20, wherein subdividing is not performed along potential branches of the segment tree data structure that are not on paths from the parent node to the one or more nodes.

28. A computer program stored on a computer-readable medium for populating nodes in segment tree data structures, the computer program comprising instructions that cause a computer to:

generate a first segment tree data structure that includes nodes covering a first time duration;

generate a second segment tree data structure that includes nodes covering a second time duration; and

reset nodes in the first segment tree data structure;

to cover a third time duration following expiration of the first time duration.

29. The computer program of claim 28, further comprising instructions that cause the computer to:

reset nodes in the second segment tree data structure to cover a fourth time duration following expiration of the second time duration.

30. The computer program of claim 28, further comprising instructions that cause the computer to:

receive a network service reservation, the network service reservation having a predetermined time duration;

determine which of the first and second segment tree data structure(s) has one or more nodes that cover the predetermined time duration; and

store data from the network service reservation using the segment tree data structure(s) determined to have one or more nodes that cover the predetermined time duration.

31. A computer program stored on a computer-readable medium for generating a segment tree data structure, the computer program comprising instructions that cause a computer to:

generate a parent node for an existing node of a segment tree data structure, the parent node having a duration that encompasses a duration of the existing node; and

delete the existing node following a duration of the existing node.

32. The computer program of claim 31, further comprising instructions that cause the computer to:

delete a descendent node of the existing node when a duration of the descendent node expires.

33. The computer program of claim 31, further comprising instructions that cause the computer to:

insert a node beneath the parent node that covers a duration following the duration of the existing node.

34. The computer program of claim 33, wherein the node inserted beneath the parent node branches off to a corresponding segment tree data structure.

35. The computer program of claim 31, further comprising instructions that cause the computer to:

receive a network service reservation, the network service reservation having a predetermined time duration;

generate one or more nodes to cover the network service reservation based on the parent node, the one or more nodes being generated by subdividing nodes of the segment tree data structure along paths from the parent node to the one or more nodes; and

store data from the network service reservation in the one or more nodes.

43. The apparatus of claim 35, wherein subdividing is not performed along potential branches of the segment tree data structure that are not on paths from the parent node to the one or more nodes.

36. An apparatus for storing data over a range of values using a segment tree data structure, the apparatus comprising circuitry which:

generates one or more nodes to cover the range of values based on a parent node in the segment tree data structure, the one or more nodes being generated by subdividing nodes of the segment tree data structure only along paths from the parent node to the one or more nodes; and

stores the data in the one or more nodes.

37. The apparatus of claim 36, wherein the data comprises data from a network service reservation and the range of values comprises a duration of the network service reservation.

38. The apparatus of claim 37, wherein the one or more nodes each has a granularity that makes it possible to cover, without exceeding, the duration of the network service reservation.

39. The apparatus of claim 36, wherein subdividing comprises generating child nodes for each subdivided node, each of the child nodes covering a portion of a duration of the subdivided node.

40. The apparatus of claim 39, wherein subdividing generates two nodes for each subdivided node, each of the two nodes covering half of the duration of the subdivided node.

41. The apparatus of claim 36, wherein the range of values defines a time duration and the one or more nodes correspond to the time duration.

42. The apparatus of claim 41, wherein, if more than one node is generated, resulting nodes when combined have a duration that corresponds to the time duration.

44. The apparatus of claim 36, wherein the circuitry comprises a processor and a memory.

45. The apparatus of claim 36 wherein the circuitry comprises hardware elements and/or programmable logic.

46. An apparatus for populating nodes in segment tree data structures, the apparatus comprising circuitry which:

generates a first segment tree data structure that includes nodes covering a first time duration;

generates a second segment tree data structure that includes nodes covering a second time duration; and

resets nodes in the first segment tree data structure to cover a third time duration following expiration of the first time duration.

47. The apparatus of claim 46, wherein the circuitry resets nodes in the second segment tree data structure to cover a fourth time duration following expiration of the second time duration.

48. The apparatus of claim 46, wherein the circuitry:

receives a network service reservation, the network service having a predetermined time duration;

determines which of the first and second segment tree data structure(s) has one or more nodes that cover the predetermined time duration; and

stores data from the network service reservation using the segment tree data structure(s) determined to have one or more nodes that cover the predetermined time duration.

49. The apparatus of claim 46, wherein the circuitry comprises a processor and a memory.

50. The apparatus of claim 46 wherein the circuitry comprises hardware elements and/or programmable logic.

51. An apparatus for generating a segment tree data structure, the apparatus comprising circuitry which:

generates a parent node for an existing node of a segment tree data structure, the parent node having a duration that encompasses a duration of the existing node; and

deletes the existing node following a duration of the existing node.

52. The apparatus of claim 51, wherein the circuitry deletes a descendent node of the existing node when a duration of the descendent node expires.

53. The apparatus of claim 51, wherein the circuitry inserts a node beneath the parent node that covers a duration following the duration of the existing node.

54. The apparatus of claim 53, wherein the node inserted beneath the parent node branches off to a corresponding segment tree data structure.

55. The apparatus of claim 51, wherein the circuitry:

receives a network service reservation, the network service reservation having a predetermined time duration;

generates one or more nodes to cover the network service reservation based on the parent node, the one or more nodes being generated by subdividing nodes of the segment tree data structure along paths from the parent node to the one or more nodes; and

stores data from the network service reservation in the one or more nodes.

56. The apparatus of claim 51, wherein the circuitry comprises a processor and a memory.

57. The apparatus of claim 51 wherein the circuitry comprises hardware elements and/or programmable logic.