Hierarchical resource management with maximum allowable allocation boundaries

• US 5,889,956 A
• Filed: 07/18/1996
• Issued: 03/30/1999
• Est. Priority Date: 07/19/1995
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited, Fujitsu Network Communications Incorporated (Fujitsu Limited)
• Inventors: Hauser, Stephen A., Caldara, Stephen A., Manning, Thomas A., Bubenik, Richard G.
• Primary Examiner(s): Ramirez, Ellis B.
• Application Number:
  US08/683,349
• Time in Patent Office: 985 Days
• Field of Search: 395/200.56, 395/200.53, 395/200.59, 395/200.8, 395/200.79
• US Class Current: 709/226
• CPC Class Codes: G06F 15/17375 One dimensional, e.g. linear array, ring
• CPC Class Codes: H04J 3/0682 by delay compensation, e.g. by compensation of propagation delay or variations thereof, by ranging
• CPC Class Codes: H04J 3/0685 Clock or time synchronisation in a node; Intranode synchronisation
• CPC Class Codes: H04L 12/4608 LAN interconnection over ATM networks
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 12/64 Hybrid switching systems
• CPC Class Codes: H04L 12/6402 Hybrid switching fabrics
• CPC Class Codes: H04L 2012/5614 User Network Interface
• CPC Class Codes: H04L 2012/5616 Terminal equipment, e.g. codecs, synch.
• CPC Class Codes: H04L 2012/5627 Fault tolerance and recovery
• CPC Class Codes: H04L 2012/5628 Testing
• CPC Class Codes: H04L 2012/5629 Admission control
• CPC Class Codes: H04L 2012/5631 Resource management and allocation
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5634 In-call negotiation
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5642 Multicast/broadcast/point-multipoint, e.g. VOD
• CPC Class Codes: H04L 2012/5643 Concast/multipoint-to-point
• CPC Class Codes: H04L 2012/5647 Cell loss
• CPC Class Codes: H04L 2012/5648 : Packet discarding, e.g. EPD, PTD
• CPC Class Codes: H04L 2012/5649 : Cell delay or jitter
• CPC Class Codes: H04L 2012/565 : Sequence integrity
• CPC Class Codes: H04L 2012/5651 : Priority, marking, classes
• CPC Class Codes: H04L 2012/5652 : Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
• CPC Class Codes: H04L 2012/5672 : Multiplexing, e.g. coding, scrambling
• CPC Class Codes: H04L 2012/5679 : Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 : Buffer or queue management
• CPC Class Codes: H04L 2012/5682 : Threshold; Watermark
• CPC Class Codes: H04L 2012/5683 : for avoiding head of line blocking
• CPC Class Codes: H04L 2012/5684 : Characteristics of traffic flows
• CPC Class Codes: H04L 2012/5685 : Addressing issues
• CPC Class Codes: H04L 41/00 : Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 41/0896 : Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/0897 : by horizontal or vertical scaling of resources, or by migrating entities, e.g. virtual resources or entities
• CPC Class Codes: H04L 41/40 : using virtualisation of network functions or resources, e.g. SDN or NFV entities
• CPC Class Codes: H04L 47/10 : Flow control; Congestion control
• CPC Class Codes: H04L 47/11 : Identifying congestion
• 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/16 : in connection oriented networks, e.g. frame relay
• CPC Class Codes: H04L 47/18 : End to end
• CPC Class Codes: H04L 47/26 : using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 47/266 : Stopping or restarting the source, e.g. X-on or X-off
• CPC Class Codes: H04L 47/29 : using a combination of thresholds
• CPC Class Codes: H04L 47/30 : in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/50 : Queue scheduling
• CPC Class Codes: H04L 47/52 : by attributing bandwidth to queues
• CPC Class Codes: H04L 47/521 : Static queue service slot or fixed bandwidth allocation
• CPC Class Codes: H04L 47/522 : Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/525 : by redistribution of residual bandwidth
• CPC Class Codes: H04L 47/56 : implementing delay-aware scheduling
• CPC Class Codes: H04L 47/621 : Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 47/6215 : Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6225 : Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 47/627 : policing
• CPC Class Codes: H04L 47/70 : Admission control; Resource allocation
• CPC Class Codes: H04L 47/722 : at the destination endpoint, e.g. reservation of terminal resources or buffer space
• CPC Class Codes: H04L 47/743 : Reaction at the end points
• CPC Class Codes: H04L 47/745 : Reaction in network
• CPC Class Codes: H04L 47/762 : triggered by the network
• CPC Class Codes: H04L 47/782 : Hierarchical allocation of resources, e.g. involving a hierarchy of local and centralised entities
• CPC Class Codes: H04L 47/805 : QOS or priority aware
• CPC Class Codes: H04L 47/822 : Collecting or measuring resource availability data
• CPC Class Codes: H04L 49/101 : using crossbar or matrix
• CPC Class Codes: H04L 49/103 : using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/106 : using space switching, e.g. crossbar or matrix
• CPC Class Codes: H04L 49/107 : using shared medium
• CPC Class Codes: H04L 49/108 : using shared central buffer
• CPC Class Codes: H04L 49/153 : ATM switching fabrics having parallel switch planes
• CPC Class Codes: H04L 49/1553 : Interconnection of ATM switching modules, e.g. ATM switching fabrics
• CPC Class Codes: H04L 49/1576 : Crossbar or matrix
• CPC Class Codes: H04L 49/20 : Support for services
• CPC Class Codes: H04L 49/201 : Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/203 : ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/205 : Quality of Service based
• CPC Class Codes: H04L 49/25 : Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/253 : using establishment or release of connections between ports
• CPC Class Codes: H04L 49/254 : Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/255 : Control mechanisms for ATM switching fabrics
• CPC Class Codes: H04L 49/256 : Routing or path finding in ATM switching fabrics
• CPC Class Codes: H04L 49/30 : Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3009 : Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3081 : ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/309 : Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/455 : Provisions for supporting expansion in ATM switches
• CPC Class Codes: H04L 49/503 : Policing
• CPC Class Codes: H04L 49/505 : Corrective measures
• CPC Class Codes: H04L 49/506 : Backpressure
• CPC Class Codes: H04L 49/508 : Head of Line Blocking Avoidance
• CPC Class Codes: H04L 49/55 : Prevention, detection or correction of errors
• CPC Class Codes: H04L 49/552 : by ensuring the integrity of packets received through redundant connections
• CPC Class Codes: H04L 49/555 : Error detection
• CPC Class Codes: H04L 49/90 : Buffering arrangements
• CPC Class Codes: H04L 49/901 : using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9047 : including multiple buffers, e.g. buffer pools
• CPC Class Codes: H04L 49/9078 : using an external memory or storage device
• CPC Class Codes: H04L 69/32 : Architecture of open systems interconnection [OSI] 7-layer type protocol stacks, e.g. the interfaces between the data link level and the physical level
• CPC Class Codes: H04L 69/322 : Intralayer communication protocols among peer entities or protocol data unit [PDU] definitions
• CPC Class Codes: H04L 69/324 : in the data link layer [OSI layer 2], e.g. HDLC
• CPC Class Codes: H04L 7/046 : using a dotting sequence
• CPC Class Codes: H04Q 11/0478 : Provisions for broadband connections
• CPC Class Codes: H04W 28/14 : using intermediate storage
• CPC Class Codes: Y10S 370/902 : Packet switching
• CPC Class Codes: Y10S 370/905 : Asynchronous transfer mode, ASN

Abstract

A system for managing resources such as buffers and bandwidth which are allocated to competing entities through two or more levels in a telecommunications network is disclosed. The system provides a tool to allocate resources for use by individual entities. Each entity may be assigned a Minimum_-- Guaranteed variable and a Maximum_-- Allowed variable. When an entity requests resources the system determines if the entity is using its respective minimum guaranteed resource allocation which is specified by the Minimum_-- Guaranteed variable. If the entity is not using its respective minimum guaranteed resource allocation, the system allocates a resource unit to the requesting entity. The system also allows a requesting entity to use additional resource units above the resource allocation specified by the Minimum_-- Guaranteed variable, provided such resource units are available. If the entity has reached its respective minimum guaranteed resource allocation, but has not reached the respective maximum allowed resource allocation specified by the Maximum_-- Allowed variable and no intervening level is using its respective maximum allowed resource allocation, then a resource unit is allocated to the requesting entity.

Claims

1. A method of hierarchical resource management for allocation of resource units to a level 0 entity through level 1 to level N entities including intervening levels, where N is greater than or equal to two, comprising:

assigning a first variable for at least one entity specifying a maximum resource allocation for the respective entity;

receiving a request from a level 0 entity for a resource unit; and

in response to a request from a level 0 entity for a resource unit, allocating said resource unit to the level 0 entity if;

a) actual resource utilization by said level 0 entity is less than the maximum resource allocation specified by the respective first variable; and

b) actual resource utilization by each of said level 1 through level N-1 entities is less than the maximum resource allocation specified by the respective first variable for each of said entities.

2. The method of hierarchical resource management of claim 1 wherein said method further includes the step of assigning a second variable for at least one entity, said second variable specifying a minimum resource allocation for the respective entity to which the second variable is assigned.

3. The method of hierarchical resource management of claim 1 including the further step of employing the method to manage a storage resource.

4. The method of hierarchical resource management of claim 3 including the further step of employing the method to manage memory.

5. The method of hierarchical resource management of claim 4 including the further step of employing the method to manage buffers in a telecommunications network.

6. The method of hierarchical resource management of claim 4 including the further step of employing the method to manage memory for storing ATM cells.

7. The method of hierarchical resource management of claim 1 including the further step of employing the method to manage channels.

8. A method of hierarchical resource management for allocating resource units to a level 0 entity through entities at levels 1 to N including intervening levels, where N is greater than or equal to two, comprising the steps of:

assigning a first variable for at least one entity specifying a maximum resource allocation for the respective entity;

assigning a second variable for at least one entity specifying a minimum resource allocation for the respective entity;

receiving a request from a level 0 entity for a resource unit; and

in response to a request from a level 0 entity for a resource unit, allocating said resource unit to the level 0 entity if actual resource utilization is less than the resource allocation specified by the respective second variable, and allocating said resource unit to the level 0 entity if;

a) actual resource utilization by said level 0 entity is less than the maximum resource allocation specified by the respective first variable; and

b) actual resource utilization by each of said level 1 through said level N-1 entities is less than the maximum resource allocation specified by the respective first variable for each of said entities.

9. A method of hierarchical resource management for allocation of resource units to a level 0 entity through level 1 to level N entities including intervening levels, where N is greater than or equal to two, comprising the steps of:

assigning a first variable for at least one entity specifying a maximum resource allocation for the respective entity;

assigning a second variable for at least one entity specifying a minimum resource allocation for the respective entity;

receiving a request from a level 0 entity for a resource unit; and

in response to a request from a level 0 entity for a resource unit;

a) allocating said resource unit to the level 0 entity provided actual resource utilization by the level 0 entity is less than the minimum resource utilization specified by the second variable, said resource unit being granted without regard to any resultant resource utilization in excess of that specified by the respective second variable at levels 1 through N; and

b) allocating said resource unit to the level 0 entity provided actual resource utilization by the level 0 entity is greater than the minimum allocation specified by the second variable, and provided resultant actual resource utilization at each of levels 1 through N will be less than the minimum resource utilization specified by the respective second variable.

10. The method of hierarchical resource management of claim 9 including the further step of employing the method to manage a storage resource.

11. The method of hierarchical resource management of claim 10 including the further step of employing the method to manage memory.

12. The method of hierarchical resource management of claim 11 including the further step of employing the method to manage buffers in a telecommunications network.

13. The method of hierarchical resource management of claim 11 including the further step of employing the method to manage memory for storing ATM cells.