Prioritized access to shared buffers

• US 6,076,112 A
• Filed: 03/09/1999
• Issued: 06/13/2000
• Est. Priority Date: 07/19/1995
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited, Fujitsu Network Communications Incorporated (Fujitsu Limited)
• Original Assignee: Fujitsu Limited, Fujitsu Network Communications Incorporated (Fujitsu Limited)
• Inventors: Hauser, Stephen A., Caldara, Stephen A., Manning, Thomas A.
• Primary Examiner(s): Sheikh, Ayaz R.
• Assistant Examiner(s): PANCHOLI, JIGAR K
• Application Number:
  US09/265,440
• Time in Patent Office: 462 Days
• Field of Search: 709/230-235, 710/52-57
• US Class Current: 709/234
• 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

In a link-level flow controlled system, a method and apparatus providing the ability to partition a buffer resource among multiple prioritized buffer subsets through definition of at least one threshold, the buffer resource being shared by a plurality of connections. Different category of service levels, in terms of delay bounds, are thus enabled. The presently disclosed link-level flow controlled system provides for zero cell loss. The shared buffer resource is divided among N priority pools, defined by N-1 threshold levels, each priority pool attributable to a respective category of service. Link-level counters and registers, disposed in a transmit element, as well as an indication of priority level associated with each connection, are employed in realizing the shared buffer resource.

Claims

1. A method for providing prioritized access to a shared buffer resource in a receiving apparatus by data cells transmitted over a link to said receiving apparatus by a sending apparatus, said method comprising the steps of:

determining a priority level of a data cell to be transmitted;

generating a first count indicative of a number of data cells transmitted to said receiving apparatus over said link for storage in said shared buffer resource;

storing at least one buffer threshold providing a maximum number of buffers allocatable to data cells of a respective priority level;

identifying which, if any, of said at least one buffer thresholds are equaled or exceeded by said first count; and

disabling transmission of said data cell to be transmitted if one of said at least one buffer threshold corresponding to said priority level of said data cell to be transmitted is equaled or exceeded by said first count.

2. The method according to claim 1, wherein said step of determining a priority level further comprises determining said priority level of said data cell to be transmitted based upon a connection of said data cell.

3. The method according to claim 1, wherein N-1 buffer thresholds are stored for every N priority levels determined.

4. The method according to claim 1, further comprising the step of modifying said first count as data cells are transmitted by said sending apparatus to said receiving apparatus over said link.

5. The method according to claim 1, wherein said step of modifying said first count further comprises modifying said first count in accordance with a value identifying the number of buffers allocated to data cells within said shared buffer resource.

6. The method according to claim 1, wherein said step of storing at least one buffer threshold further comprises dynamically adjusting said at least one buffer threshold according to an empirical analysis of data cells to be transmitted by said sending apparatus.

7. The method according to claim 6, wherein said step of dynamically adjusting said at least one buffer threshold further comprises dynamically adjusting said at least one buffer threshold according to an empirical analysis of priorities of data cells to be transmitted by said sending apparatus.

8. The method according to claim 1, wherein said step of storing at least one buffer threshold further comprises dynamically adjusting said at least one buffer threshold according to an empirical analysis of utilization of said shared buffer resource.

9. The method according to claim 1, further comprising the step of establishing a maximum number of data cells storable in said shared buffer resource.

10. The method according to claim 9, wherein said step of disabling transmission further comprises disabling transmission of said data cell if said first count equals or exceeds said maximum number of data cells storable.

11. The method according to claim 1, wherein said data cells are ATM cells.

12. The method according to claim 1, wherein said data cells are of a predetermined, fixed length.

13. A method of providing prioritized access by data cells of a sending element to a shared buffer resource in a receiving element via a communications resource, said method comprising the steps of:

defining a maximum number of priority allocated buffers available in said shared buffer resource for each of a plurality of data cell priorities and storing each of said maximum numbers;

storing a value indicative of a number of data cells transmitted by said sending element to said receiving element via said communication resource for storage in said shared buffer resource;

modifying said value as data cells are transmitted to said shared buffer resource;

identifying a priority assigned to a first data cell; and

transmitting said first data cell by said sending element to said receiving element via said communications resource for storage in said shared buffer resource if said value is less than a respective maximum number of priority allocated buffers.

14. The method according to claim 13, further comprising the step of dynamically adjusting one or more of said maximum numbers of priority allocated buffers according to an empirical analysis of data cells to be transmitted.

15. The method according to claim 14, wherein said step of dynamically adjusting one or more of said maximum numbers of priority allocated buffers further comprises dynamically adjusting said maximum numbers of priority allocated buffers according to an empirical analysis of priorities of said data cells of said sending element.

16. The method according to claim 13, further comprising the step of dynamically adjusting one or more of said maximum numbers of priority allocated buffers according to an empirical analysis of utilization of said shared buffer resource.

17. The method according to claim 13, wherein said step of identifying a priority further comprises identifying said priority assigned to said first data cell based upon a connection of said first data cell.

18. The method according to claim 13, wherein for N data cell priorities, said step of defining a maximum number further comprises:

defining one maximum number of priority allocated data cells equivalent to a maximum buffer resource capacity; and

defining N-1 maximum number of priority allocated data cells equivalent to data cell priority thresholds.

19. The method according to claim 13, wherein said step of modifying said value further comprises receiving the number of buffers allocated to data cells within said shared buffer resource and modifying said value in accordance therewith.

20. The method according to claim 13, wherein said data cells are ATM cells.

21. The method according to claim 13, wherein said data cells are of a predetermined, fixed length.

22. A prioritized buffer sharing apparatus comprising:

a communications medium having a sending end and a receiving end;

a sending element at said sending end of said communications medium for transmitting a data cell over said communications medium; and

a receiving element at said receiving end of said communications medium for receiving said data cell, said receiving element having a prioritized shared buffer resource associated therewith for storing said data cell,

wherein said sending element analyzes said data cell to determine a priority associated therewith, and

wherein said sending element transmits said data cell to said receiving element via said communications medium for storage in said shared buffer resource if buffers in said shared buffer resource are available for storing data cells of like priority.

23. The prioritized buffer sharing apparatus according to claim 22, wherein said sending element further comprises a processing element and a memory element in which is maintained, by said processing element:

a first value representative of a maximum number of data cells storable in said prioritized shared buffer resource;

a second value representative of a number of buffers transmitted to said prioritized shared buffer resource for storage therein; and

at least one threshold value each representative of a maximum number of data cells of a respective priority which are storable in said prioritized shared buffer resource.

24. The prioritized buffer sharing apparatus according to claim 23, wherein said processing element prohibits transmission of said data cell from said sending element to said receiving element if said second value is not less than said first value.

25. The prioritized buffer sharing apparatus according to claim 23, wherein said processing element prohibits transmission of said data cell if said second value is not less than a respective threshold value for the priority of said data cell.

26. The prioritized buffer sharing apparatus according to claim 23, wherein said at least one threshold value is dynamically adjustable by said processing element based upon an empirical analysis of data cells to be transmitted to said shared buffer resource.

27. The prioritized buffer sharing apparatus according to claim 26, wherein said at least one threshold value is dynamically adjustable by said processing element based upon an empirical analysis of priorities of data cells to be transmitted to said shared buffer resource.

28. The prioritized buffer sharing apparatus according to claim 23, wherein said at least one threshold value is dynamically adjustable by said processing element based upon an empirical analysis of utilization of said shared buffer resource.

29. The prioritized buffer sharing apparatus according to claim 23, wherein there are N possible data cell priorities and N-1 threshold values.

30. The prioritized buffer sharing apparatus according to claim 23, wherein said second value is updated by said processing element according to a number of data cells presently stored within said shared buffer resource.

31. The prioritized buffer sharing apparatus according to claim 22, wherein said data cell is an ATM cell.

32. The prioritized buffer sharing apparatus according to claim 22, wherein said data cell is of a predetermined, fixed length.