Apparatus and method for time multiplexing a resource among a plurality of entities
First Claim
1. Apparatus for time multiplexing a resource among one or more entities, the apparatus comprising:
- a set of at least two servers for providing use of the resource to the entities for intervals of time, at least one of the servers being capable of activating another server in the set and the at least one server comprising;
means for associating at least one of the entities with the server;
means for associating a set of the intervals of time with the server; and
means operating when the server is active to make the resource available to the at least one associated entity for a subset of the set of intervals of time and to activate the other server for intervals of time remaining in the set of intervals of time.
1 Assignment
0 Petitions
Accused Products
Abstract
Apparatus and methods for time multiplexing a resource among a plurality of entities at average rates and with deterministic delays between accesses to the resource by an entity. An entity accessing the resource receives a time slot on the resource; a fixed number of time slots constitute a frame. Each entity receives a fixed allocation of time slots in the frame. When an entity has work for the resource to do, it receives access to the resource for a number of slots in each frame equal to the lesser of the number of slots required to do the work and the number of slots in the allocation. A rate-controlled server is disclosed which defines a frame and allocations therein, as well as a hierarchy of servers which combines rate-controlled traffic with best effort traffic. In the hierarchy, a rate-controlled server activates a round-robin server when the entities served by the rate-controlled server do not require all the slots in a frame. A hierarchy of rate-controlled servers is further disclosed which permits access to the resource at widely-differing average rates. In that hierarchy, a number of slots in the frame for a given member of the hierarchy are reserved for the next member down of the hierarchy and the next member down is active only during those slots. Further disclosed are nodes of ISDN networks employing ATM which incorporate the servers and hierarchies thereof.
-
Citations
41 Claims
-
1. Apparatus for time multiplexing a resource among one or more entities, the apparatus comprising:
-
a set of at least two servers for providing use of the resource to the entities for intervals of time, at least one of the servers being capable of activating another server in the set and the at least one server comprising; means for associating at least one of the entities with the server; means for associating a set of the intervals of time with the server; and means operating when the server is active to make the resource available to the at least one associated entity for a subset of the set of intervals of time and to activate the other server for intervals of time remaining in the set of intervals of time. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A method of time multiplexing a resource among one or more entities by providing the resource to the entities for fixed intervals of time, the method comprising the steps of:
-
establishing a first set of the intervals of time; associating subsets of the first set with first certain of the entities; and repeatedly providing the resource to the first certain entities for the set of intervals of time; and during each repetition of the set of intervals of time, providing the resource to a given one of the first certain entities for a number of intervals of time no greater than the number of intervals in the subset associated with the given entity and providing the resource to at least one of the entities which is not one of the first certain entities for intervals of time remaining in the set of intervals of time.
-
-
13. Apparatus for controlling the flow of cells of digitized data in a plurality of virtual circuits, the apparatus comprising:
-
at least two sets of storage means for storing the cells, each storage means being associated with a virtual circuit of the plurality of virtual circuits; receiving means for receiving the cells and placing each cell in the storage means associated with the virtual circuit which is carrying the cell; transmitting means for transmitting the cells, each cell being transmitted in an interval of time; and a set of at least two servers for causing the transmitting means to transmit cells from the storage means when active, at least one of the servers being capable of activating another server in the set and the at least one server comprising means for associating one of the sets of storage means with the server; means for associating a set of the intervals of time with the server; and means operating when the server is active to cause the transmitting means to transmit cells from storage means in the associated set of storage means for a subset of the intervals of time and to activate the other server for intervals of time remaining in the set of intervals of time. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. A network for transferring cells of digitized data in virtual circuits operating at controlled rates, the network comprising:
-
one or more nodes for receiving and transmitting a plurality of the virtual circuits including one or more virtual circuits operating at a controlled rate, each node comprising at least two sets of storage means for storing the cells, each storage means in at least one of the sets of storage means being associated with one of the controlled rate virtual circuits; receiving means for receiving the cells and placing each cell in the storage means associated with the virtual circuit which is carrying the cell; transmitting means for transmitting the cells, each cell being transmitted in an interval of time; and a set of at least two servers for causing the transmitting means to transmit cells from the storage means when active, at least one of the servers being capable of activating another server in the set and the at least one server comprising means for associating the set of storage means associated with the controlled rate virtual circuits with the server; means for associating a periodically repeating set of the intervals of time with the server; and means operating when the server is active to cause the transmitting means to transmit cells from storage means in the associated set of storage means for a subset of the intervals of time and to activate the other server for intervals of time remaining in the set of intervals of time. - View Dependent Claims (25, 26, 27, 28)
-
-
29. A method for adjusting the rate of a rate-controlled virtual circuit in a network of the type wherein the rate of the rate-controlled virtual circuit is established by associating the virtual circuit with a subset of one of a set of periodically-repeating sets of intervals of time, the method comprising the steps of:
-
determining during a longest period belonging to the periodically-repeating sets of intervals of time whether the rate-controlled virtual circuit is using all of the intervals in its subset; if it is not, determining a size of a new subset and/or a period of the set of intervals of time such that the virtual circuit will use more of the intervals of time in the new subset; and setting the size of the subset and/or the period of the set as determined at the end of one of the longest periods.
-
-
30. A method for setting the rate of a rate controlled virtual circuit to a given rate or adding a rate controlled virtual circuit having the given rate in a network of the type wherein the rate of the rate controlled virtual circuit is established by associating the virtual circuit with a subset of one of a hierarchical set of periodically-repeating sets of intervals of time, the set of intervals of time in each level of the hierarchy but the highest being made up of intervals of time from a subset of the next highest set in the hierarchy, the method comprising the steps of:
-
beginning with the level at which the virtual circuit is being set or added, determining whether setting the virtual circuit to the given rate or adding the virtual circuit will increase the total number of intervals of time in the subset such that the number of intervals of time in all of the subsets exceed the number of intervals of time in the set to which the subset belongs; if either action does, adding at least one interval of time for the set to which the subset belongs to the next higher level of the hierarchy and adjusting the number of intervals of time in the subset for the virtual circuit being added or set until proper rate is reached; and if adding intervals of time to the subset in the next level of the hierarchy increases the total number of intervals of time in the subset such that the number of intervals in all of the subsets exceed the number of intervals of time in the set to which the subset belongs, repeating steps 1 and 2 for that level and the next higher level.
-
-
31. Apparatus for making a time-multiplexed resource available to an entity at a changeable guaranteed average rate, the apparatus comprising:
-
means for associating pieces of work belonging to the entity with the apparatus; means for associating a set of the intervals of time with the apparatus; means for changeably associating a subset of the set of intervals of time with the entity; and means for repeatedly providing the associated pieces of work to the resource for the set of intervals of time, the number of intervals of time provided for the associated pieces of work in a given one of the repeated set of intervals of time being equal to the current number of the associated pieces of work if that number is less than the number of intervals of time in the subset associated with the entity and otherwise the number of intervals of time in the subset associated with the entity. - View Dependent Claims (32, 33)
-
-
34. A method of making a time-multiplexed resource available to an entity at a changeable guaranteed average rate, the method comprising the steps of:
-
establishing a set of the intervals of time; associating pieces of work belonging to the entity with the apparatus; changeably associating a subset of the set of intervals of time with the entity; and repeatedly providing the associated pieces of work to the resource for the set of intervals of time, the number of intervals of time provided for the associated pieces of work in a given one of the repeated set of intervals of time being equal to the current number of the associated pieces of work if that number is less than the number of intervals of time in the subset associated with the entity and otherwise the number of intervals of time in the subset associated with the entity. - View Dependent Claims (35)
-
-
36. Apparatus for providing a changeable guaranteed average rate of flow of cells of digitized data in one or more virtual circuits, the apparatus comprising:
-
at least one storage means for storing the cells, each storage means being associated with one of the virtual circuits; receiving means for receiving the cells and placing each cell in the storage means associated with the virtual circuit which is carrying the cell; transmitting means for transmitting the cells, each cell being transmitted in an interval of time; and a server for causing the transmitting means to transmit cells from the storage means, the server comprising means for associating the storage means with the server; means for changeably associating a set of the intervals of time with the server; means for associating a subset of the set of intervals of time with each of the storage means; and means for repeatedly causing the transmitting means to transmit cells from the associated storage means for the set of intervals of time, the number of the intervals of time in a given one of the repeated sets of intervals of time which are used for cells from a given one of the storage means being the number required to empty the given storage means if that number is less than the number of intervals of time in the subset associated with the given storage means and otherwise the number of intervals of time in the subset associated with the given storage means. - View Dependent Claims (37, 38)
-
-
39. A network for transferring cells of digitized data in virtual circuits operating at changeable guaranteed average rates, the network comprising:
-
one or more nodes for receiving and transmitting one or more virtual circuits operating at a controlled rate, each node comprising at least one storage means for storing the cells, each storage means being associated with one of the virtual circuits; receiving means for receiving the cells and placing each cell in the storage means associated with the virtual circuit which is carrying the cell; transmitting means for transmitting the cells, each cell being transmitted in an interval of time; and a server for causing the transmitting means to transmit cells from the storage means, the server comprising means for associating the storage means with the server; means for changeably associating a set of the intervals of time with the server; means for associating a subset of the set of intervals of time with each of the storage means; and repeatedly causing the transmitting means to transmit cells from the associated storage means for the set of intervals of time, the number of the intervals of time in a given one of the repeated set of intervals of time which are used for cells from a given one of the storage means being the number required to empty the given storage means if that number is less than the number of intervals of time in the subset associated with the given storage means and otherwise the number of intervals of time in the subset associated with the given storage means. - View Dependent Claims (40, 41)
-
Specification