Digital network including mechanism for grouping virtual message transfer paths having similar transfer service rates to facilitate efficient scheduling of transfers thereover

• US 5,995,511 A
• Filed: 04/05/1996
• Issued: 11/30/1999
• Est. Priority Date: 04/05/1996
• Status: Expired due to Term

• Current Assignee: Ericsson AB (Telefonaktiebolaget LM Ericsson)
• Original Assignee: FORE Systems, Inc. (Cornhill Corp. Holdings LLP)
• Inventors: Zhou, Fan, Brownhill, Robert J., Bennett, Jon C.R., Ganmukhi, Mahesh N.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US08/628,206
• Time in Patent Office: 1,334 Days
• Field of Search: 370/400, 370/407, 370/411, 370/412, 370/438, 370/351, 370/391, 370/396, 370/517
• US Class Current: 370/412
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 49/107 using shared medium
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A queue control system is disclosed for use in connection with the transfer of information, in the form of information transfer units, in a digital network. The network provides a plurality of service rate classes, based on, for example transmission rates for the various paths. The information buffer control subsystem includes a information transfer unit receiver, a information transfer unit buffer and a group controller. The information transfer unit receiver receives the information transfer units, and the buffer is provided to buffer the received information transfer units prior to transmission. The group controller controls the buffering of information transfer units received by the information transfer unit receiver in the buffer. In that operation, the group controller aggregates the information transfer units for each path in the buffer according to respective service rate classes, in particular aggregating the information transfer units for each path in a queue and further aggregating the queues for the paths associated with each service rate class in a queue. A transmission scheduler is also disclosed for use in transferring information, in the form of information transfer units, each associated with a path, in a digital network. The network provides a plurality of service rate classes, based on, for example, transmission rates for the various paths. The information transfer units for each path in a path queue, and the path queues for the paths associated with each service rate class are aggregated in a service rate queue. The transmission scheduler includes a information transfer unit selector for selecting from among the service rate queues, one path queue to provide a information transfer unit for transmission, and a information transfer unit transmitter for transmitting the information transfer unit provided by the selected path queue.

Claims

1. A queue control system for use in connection with transfer of information transfer units, in a digital network, the network providing a plurality of service rates, the queue control subsystem comprising:

A. an information transfer unit receiver for receiving information transfer units,

B. a buffer for buffering information transfer units received by said information transfer unit receiver, and

C. a group controller for controlling the buffering of information transfer units in said buffer, the group controller aggregating the information transfer units in the buffer into a plurality of groups each associated with a respective one of said service rates, with all of the information transfer units associated with one of said service rates being aggregated into the same one of said plurality of groups.

2. The queue control system as defined in claim 1 in which each information transfer unit comprises a cell.

3. The queue control system as defined in claim 2 in which all of said cells have a predetermined length.

4. The queue control system as defined in claim 1 in which each said information transfer unit is associated with a path identifier identifying a path through said network, each path having an associated one of said plurality of service rates, the group controller aggregating the information transfer units in said buffer in groups according to their associated path identifiers, and further according to their respective service rates.

5. The queue control system as defined in claim 4 in which said group controller aggregates information transfer units associated with a path identifier in a path queue in said buffer associated with said path identifier.

6. The queue control system as defined in claim 5 in which said path queue has a path queue tail member, and in which said group controller, in response to receipt of one of said information transfer units adds the information transfer unit to the path queue for the path queue associated with the information transfer unit'"'"'s associated path identifier, as the path queue tail member.

7. A queue control system for use in connection with transfer of information transfer units, in a digital network, the network providing a plurality of service rates, each said information transfer unit being associated with a path identifier identifying a path through said network, the queue control subsystem comprising:

A. an information transfer unit receiver for receiving information transfer units,

B. a buffer for buffering information transfer units received by said information transfer unit receiver,

C. a group controller for controlling the buffering of information transfer units in said buffer, the group controller aggregating the information transfer units in the buffer into a plurality of groups each associated with a respective one of said service rates, the group controller aggregating the information transfer units in said buffer in groups according to their associated path identifiers in a path queue in said buffer associated with said path identifier, and

D. a resource allocator responsive to receipt by said information buffer control subsystem of one of said information transfer units associated with a new path identifier for providing the group controller with one of said path queues for said information transfer unit.

8. The queue control system as defined in claim 7 in which said resource allocator maintains a free list comprising a plurality of free queue entries, the resource allocator providing said group controller with one of said free queue entries in response to receipt by said information buffer control subsystem of said information transfer unit associated with said new path identifier, the group controller using the free queue entry to establish said path queue for said new path identifier.

9. The queue control system as defined in claim 8 in which

A. the group controller, in response to its determining that said path queue does not contain any information transfer units, provides the path queue to said resource allocator, and

B. the resource allocator, in response to receiving one of said path queues from the group controller, loads the path queue as one of said free queue entries into its free list.

10. The queue control system as defined in claim 9 in which said group controller aggregates path queues into at least one of said groups associated with one of said service rates.

11. The queue control system as defined in claim 10 in which at least one of said groups comprises a group list.

12. The queue control system as defined in claim 11 in which said resource allocator maintains a free group list comprising a plurality of free group entries, the resource allocator providing said group controller with a free group entry from said plurality of free group entries in response to receipt by said information buffer control subsystem of said information transfer unit associated with a path identifier having a new service rate, the group controller using said free group entry to establish a new group for said new service rate.

13. The queue control system as defined in claim 12 in which

A. the group controller, in response to its determining that one of said groups does not contain any path queues, provides the group entry for said group to said resource allocator, and

B. the resource allocator loads the group entry provided thereto by the group controller as a free group entry into its free group list.

14. A queue control system for use in connection with transfer of information transfer units, in a digital network, the network providing a plurality of service rates, each information transfer unit being associated with a path identifier identifying a path through said network, and each path being associated with a service rate, the queue control subsystem comprising:

A. an information transfer unit receiver for receiving information transfer units,

B. a buffer for buffering information transfer units received by said information transfer unit receiver, and

C. a group controller for controlling the buffering of information transfer units in said buffer, the group controller aggregating the information transfer units in the buffer into a plurality of groups each associated with a respective one of said service rates, said group controller maintaining a group associated with each service rate for the paths for which information buffer control subsystem is receiving information transfer units, each group comprising a list of path queues each associated with a path and including information transfer units received by said information transfer unit receiver associated with said path.

15. The queue control system as defined in claim 14 in which each path queue has an associated service time stamp, the group controller maintaining said list of path queues in an order defined by said time stamp.

16. The queue control system as defined in claim 15 in which said group controller further includes a transmission selector for selecting information transfer units for transmission, the transmission selector selecting one of said path queues in said group based on the path queue'"'"'s respective time stamp.

17. The queue control system as defined in claim 16 in which each said list has a head path queue comprising one of the path queues in the respective list, and which said transmission selector comprises:

A. a group selector for identifying one of said groups as a selected group in response to the time stamp of the groups'"'"' respective head path queues,

B. an information transfer unit selector for selecting one of said information transfer units from the head path queue of the selected group for transmission.

18. The queue control system as defined in claim 17 in which said group selector selects as the selected group the one of said groups for which the time stamp of the group'"'"'s respective head path queues has the lowest value.

19. The queue control system as defined in claim 18 in which said transmission selector further includes an eligibility determination element for identifying from among said groups a set of eligible groups in response to the time stamp of the groups'"'"' respective head path queues, the group selector identifying said selected group from among said eligible groups.

20. The queue control system as defined in claim 19 further comprising a clock for providing a current time value, the eligibility determination element using the current time value, the time stamps associated with the respective groups'"'"' head path queues and the respective groups'"'"' service rates in identifying said set of eligible groups.

21. The queue control system as defined in claim 20 in which the eligibility determination element, in determining whether said group is one of said eligible groups, decrements the time stamp associated with the group'"'"'s head path queue by an amount corresponding to the group'"'"'s service rate to generate an eligible time value, and determines whether the group is eligible in response to a comparison of the eligible time value to said current time value.

22. The queue control system as defined in claim 21 in which the eligibility determination element determines that said group is one of said eligible groups if the group'"'"'s eligible time value is less than said current time value.

23. The queue control system as defined in claim 22 in which, if the eligibility determination element determines that no group is a said eligible group, increments the clock so that at least one group is a said eligible group.

24. The queue control system as defined in claim 19 for use in said network including an unregulated service rate, which said group controller further establishing an unregulated group for paths associated with the unregulated service rate, the transmission selector selecting one of said information transfer units for transmission from said unregulated group if the eligibility determination element determines that no group is a said eligible group.

25. The queue control system as defined in claim 24 in which each path includes a path identifier having one of a plurality of path identifier values, and in which said unregulated group is in the form of a bit map comprising a plurality of bits, each associated with one of said path identifier values, each bit having a path present value and a path not present value, the group controller conditioning the bit for the path associated with the path identifier value if the path is associated with the unregulated group.

26. The queue control system as defined in claim 25 in which said unregulated group further includes an upper level bit map comprising a plurality of upper level bits, each upper level bit being associated with a plurality of said bits of said bit map, the group controller further conditioning the upper level bit associated with the bit of the bit map if the path is associated with the unregulated group.

27. The queue control system as defined in claim 17 in which each said list further includes a tail path queue, and said transmission selector further includes a group list reorder element for reorders the list associated with the selected group so that the path queue comprising the head path queue will be linked to the list as the tail path queue.

28. The queue control system as defined in claim 27 in which the group list reorder element further increments the time stamp of the head path queue by an amount corresponding to the selected group'"'"'s service rate prior while reordering the list associated with the selected group.

29. The queue control system as defined in claim 28 in which said group list reorder element, prior to reordering, further determines whether the head path queue is empty and if so eliminates it from the associated group.

30. The queue control system as defined in claim 15 in which each said list comprises a first list, at least one group further including a second list, the group controller connecting path queues for paths newly associated with the group'"'"'s service rate to said second list.

31. The queue control system as defined in claim 30, further including a transmission selector for selecting information transfer units for transmission, the transmission selector selecting one of said path queues in a said group based on the respective time stamps, the transmission selector comprising:

A. a group selector for identifying one of said groups as a selected group in response to the time stamp of the group'"'"'s respective head path queues of each of said lists,

B. an information transfer unit selector for selecting an information transfer unit from the head path queue of the selected group for transmission.

32. The queue control system as defined in claim 31 in which said transmission selector selects as the selected group the one of said groups for which the time stamp of the groups'"'"' respective head path queues for each of said group'"'"'s lists has the lowest value.

33. The queue control system as defined in claim 32 in which said transmission selector further includes an eligibility determination element for identifying from among said groups a set of eligible groups in response to the time stamp of the groups'"'"' respective head path queues for each of said group'"'"'s lists, the group selector identifying said selected group from among said eligible groups.

34. The queue control system as defined in claim 33 further comprising a clock for providing a current time value, the eligibility determination element using the current time value, the time stamps associated with the respective groups'"'"' head path queues of each of the group'"'"'s lists and the respective groups'"'"' service rates in identifying said set of eligible groups.

35. The queue control system as defined in claim 34 in which the eligibility determination element, in determining whether one of said groups is one of said eligible groups, decrements the time stamp associated with the group'"'"'s head path queue by an amount corresponding to the group'"'"'s service rate to generate an eligible time value, and determines whether the group is eligible in response to a comparison of the eligible time value to said current time value.

36. The queue control system as defined in claim 31 in which each said group'"'"'s first list further includes a tail path queue, and said transmission selector further includes a group list reorder element for reordering the lists associated with the selected group so that the path queue comprising the head path queue of the second list will be linked to the list as the tail path queue of the first list.

37. The queue control system as defined in claim 30 in which at least one group further includes a third list, the group controller connecting path queues for paths newly associated with the group'"'"'s service rate to one of said second list or said third list based on the path queue'"'"'s respective time stamp.

38. The queue control system as defined in claim 37 further comprising a clock for generating a current time value, and in which the second list corresponds to an early list and said third list corresponds to a late list, the group controller connecting path queues for paths newly associated with the group'"'"'s service rate to said early list if the path'"'"'s associated time stamp is greater than said current time value, and otherwise to the late list.

39. A transmission scheduler for use in transferring information, in the form of information transfer units, in a digital network, the network providing a plurality of service rates, each information transfer unit being associated with a path identifier identifying a path through said network, each path being associated with a service rate and a time stamp, the transmission scheduler comprising:

A. a transmission selector for selecting information transfer units for transmission, the transmission selector selecting said path based on the path queue'"'"'s respective time stamp and service rate, and

B. an information transfer unit transmitter for transmitting the information transfer unit provided by the transmission selector.

40. The transmission scheduler as defined in claim 39 in which each information transfer unit comprises a cell.

41. The transmission scheduler as defined in claim 40 in which all of said cells have a predetermined length.

56. The transmission scheduler as defined in claim 39 in which at least one path is provided by another transmission scheduler.

42. A transmission scheduler for use in transferring information, in the form of information transfer units, in a digital network, the network providing a plurality of service rates, each information transfer unit being associated with a path identifier identifying a path through said network, each path being associated with a service rate and a time stamp, information transfer units for paths associated with corresponding service rates being maintained in a group associated with each service rate, each group comprising a list of path queues each associated with a path and including information transfer units received by said information transfer unit receiver associated with said path, the transmission scheduler comprising:

A. a transmission selector for selecting information transfer units for transmission, the transmission selector selecting said path based on the path queue'"'"'s respective time stamp and service rate, the transmission selector selecting paths for transmission from among said groups, and

B. an information transfer unit transmitter for transmitting the information transfer unit provided by the transmission selector.

43. The transmission scheduler as defined in claim 42 in which each said list has a head path queue comprising one of the path queues in the respective list, and which said transmission selector comprises:

A. a group selector for identifying one said groups as a selected group in response to the time stamp of the groups'"'"' respective head path queues,

B. an information transfer unit selector for selecting an information transfer unit from the head path queue of the selected group for transmission.

44. The transmission scheduler as defined in claim 43 in which said group selector selects as the selected group the one of said groups for which the time stamp of the groups'"'"' respective head path queues has the lowest value.

45. The transmission scheduler as defined in claim 44 in which said transmission selector further includes an eligibility determination element for identifying from among said groups a set of eligible groups in response to the time stamp of the groups'"'"' respective head path queues, the group selector identifying said selected group from among said eligible groups.

46. The transmission scheduler as defined in claim 45 further comprising a clock for providing a current time value, the eligibility determination element using the current time value, the time stamps associated with the respective groups'"'"' head path queues and the respective groups'"'"' service rates in identifying said set of eligible groups.

47. The transmission scheduler as defined in claim 46 in which the eligibility determination element, in determining whether one of said groups is one of said eligible groups, decrements the time stamp associated with the group'"'"'s head path queue by an amount corresponding to the group'"'"'s service rate to generate an eligible time value, and determines whether the group is eligible in response to a comparison of the eligible time value to said current time value.

48. The transmission scheduler as defined in claim 47 in which the eligibility determination element determines that a said group is one of said eligible groups if the group'"'"'s eligible time value is less than said current time value.

49. The transmission scheduler as defined in claim 47 in which, if the eligibility determination element determines that no group is a said eligible group, increments the clock so that at least one group is a said eligible group.

50. The transmission scheduler as defined in claim 43 for use in the network including an unregulated service rate, which said group controller further establishes an unregulated group for paths associated with the unregulated service rate, the transmission selector selecting said path from said unregulated group for which an information transfer unit is to be transmitted if the eligibility determination element determines that no group is a said eligible group.

51. The transmission scheduler as defined in claim 50 in which each path includes a path identifier having one of a plurality of path identifier values, and in which said unregulated group is in the form of a bit map comprising a plurality of bits, each associated with one of said path identifier values, each bit having a path present value and a path not present value, the transmission scheduler selecting a path if its associated bit has the path present value.

52. The transmission scheduler as defined in claim 50 in which the bits of said bit map define a series of bits, the transmission scheduler testing successive bits of the series to identify a bit having the path present value, the transmission scheduler selecting said path associated with said identified bit.

53. The transmission scheduler as defined in claim 52 in which in which said unregulated group further includes an upper level bit map comprising a series of upper level bits, each upper level bit being associated with a series of bits of said bit map, the upper level bit further being conditioned to the path present value if at least one associated bit of the bit map is conditioned to the path present value, the transmission scheduler, testing the upper level bit associated with a series of bits and skipping testing of the series associated with said upper level bit which has the path not present value.

54. The transmission scheduler as defined in claim 51 in which each said list further includes a tail path queue, and said transmission selector further includes a group list reorder element for reordering the list associated with the selected group so that the path queue comprising the head path queue will be linked to the list as the tail path queue.

55. The transmission scheduler as defined in claim 54 in which the group list reorder element further increments the time stamp of the head path queue by an amount corresponding to the selected group'"'"'s service rate prior while reordering the list associated with the selected group.