Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2000-09-27
2004-07-06
Vincent, David (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S437000, C709S226000
Reexamination Certificate
active
06760306
ABSTRACT:
BACKGROUND
This invention relates to storing data, such as the duration of a network service reservation, using a segment tree data structure.
Segment tree data structures are used to store information over ranges of data. A segment tree data structure includes a parent node and typically one or more “descendent” nodes, which are generated based on the parent node. The one or more descendent nodes each stores a subset of the range of data stored in the parent node. When combined, the range of data that can be stored in the descendent nodes equals that which can be stored in the parent node.
SUMMARY
Network service reservations are made over time periods. Segment tree data structures therefore can be used to store the network service reservations over time periods.
In general, in one aspect, the invention is directed to storing data over a range of values, such as the time period of a network service reservation, 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.
This aspect of the invention may include one or more of the following features. The range of values is a duration of the network service reservation. The one or more nodes each has a granularity that makes it possible to cover, without exceeding, the duration of the network service reservation. Subdividing the nodes is performed by generating child nodes for each subdivided node. Each of the child nodes covers a portion of a duration of the subdivided node.
Two nodes are generated for each subdivided node. Each of the two nodes covers half of the duration of the subdivided node. The range of values defines a time duration and the one or more nodes correspond to the time duration. If more than one node is generated, resulting nodes when combined have a duration that corresponds to the time duration. 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.
In general, in another aspect, the invention is directed to populating nodes in segment tree data structures to cover continuous time durations. This aspect of the invention features generating a first segment tree data structure that includes nodes covering a first time duration and generating a second segment tree data structure that includes nodes covering a second time duration. In this aspect, nodes in the first segment tree data structure are reset to cover a third time duration following expiration of the first time duration.
This aspect of the invention may include one or more of the following features. Nodes in the second segment tree data structure are reset to cover a fourth time duration following expiration of the second time duration. A network service reservation is received. The network service has a predetermined time duration. It is determined which of the first and second segment tree data structure(s) has one or more nodes that cover the predetermined time duration. Data from the network service reservation is stored using the segment tree data structure(s) determined to have one or more nodes that cover the predetermined time duration.
In general, in another aspect, the invention is directed to generating a segment tree data structure. This aspect of the invention features generating a parent node for an existing node of a segment tree data structure to cover the duration that the existing node cannot cover. The parent node has a duration that encompasses a duration of the existing node. The existing node is deleted following a duration of the existing node.
This aspect of the invention may include one or more of the following features. A descendent node of the existing node is deleted when a duration of the descendent node expires. A node is inserted beneath the parent node that covers a duration following the duration of the existing node. The node inserted beneath the parent node branches off to a corresponding segment tree data structure.
A network service reservation is received. The network service reservation has a predetermined time duration. One or more nodes are generated to cover the network service reservation based on the parent node. The one or more nodes are generated by subdividing nodes of the segment tree data structure along paths from the parent node to the one or more nodes. Data from the network service reservation is stored in the one or more nodes.
In general, in another aspect, the invention is directed to a computer-readable medium storing a data structure. The data structure features a plurality of nodes arranged in a tree structure. The plurality of nodes includes a parent node relating to a range of values and one or more final nodes. Each of the one or more final nodes relates to a subset of the range of values. The data structure stores a predetermined range of values in the one or more final nodes. 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.
This aspect of the invention may include one or more of the following features. The predetermined range of values includes data from a network service reservation. 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.
REFERENCES:
patent: 5644740 (1997-07-01), Kiuchi
patent: 5701137 (1997-12-01), Kiernan et al.
patent: 5794006 (1998-08-01), Sanderman
patent: 5806056 (1998-09-01), Hekmatpour
patent: 5825944 (1998-10-01), Wang
patent: 2002/0124082 (2002-09-01), San Andres et al.
Schelén, Olov. “Quality of Service Agents in the Internet,” Div. of Computer Comm., Dept. of Computer Science and Electrical Engineering, Luleå University of Technology, Sweden, Aug. 1998, pp iii-107.
Edwards Eric
Pan Yin
Villarica Al
Fish & Richardson P.C.
Nortel Networks Limited
Vincent David
LandOfFree
Method for reserving network resources using a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for reserving network resources using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for reserving network resources using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3222141