Method and apparatus for providing buffer state flow control at the link level in addition to flow control on a per-connection basis

• US 6,256,674 B1
• Filed: 03/09/1999
• Issued: 07/03/2001
• 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., Hunt, Douglas H., Strouble, Raymond L.
• Primary Examiner(s): Harrell, Robert B.
• Application Number:
  US09/265,255
• Time in Patent Office: 847 Days
• Field of Search: 370/428, 370/429, 709/200, 709/214, 709/215, 709/232
• US Class Current: 709/232
• 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 method and apparatus for providing buffer state accounting at a link level, otherwise known as link flow control, in addition to flow control at the virtual connection level. Link flow control enables receiver cell buffer sharing while maintaining per-connection bandwidth with lossless cell transmission. High link level update frequency is enabled without a significant sacrifice in overall link forward bandwidth. A higher and thus more efficient utilization of receiver cell buffers is achieved.

Claims

1. A method of sharing a finite number of buffers within a receiver, said receiver being connected to a transmitter via a flow controlled connection, said method comprising the steps of:

dynamically adjusting a number of buffers available to said connection;

generating a first count indicative of the number of data cells transmitted through said connection by said transmitter to said receiver;

generating a second count indicative of data cells currently being transmitted through said connection by said transmitter to said receiver and indicative of data cells not known to be released from a subset of said buffers in said receiver;

generating a third count indicative of the total number of buffers in said receiver presently storing data cells;

generating a fourth count indicative of data cells transmitted from said transmitter and released from buffers in said receiver;

dynamically adjusting a number of data cells releasable from buffers in said receiver during a first interval; and

storing a number of data cells actually released from buffers in said receiver during said first interval.

2. The method according to claim 1, further comprising the step of:

dynamically adjusting a number of buffers available for storage of data cells received from said transmitter via said connection.

3. The method according to claim 2, wherein said number of buffers available for storage of data cells received from said transmitter is dynamically adjusted based upon current buffer demands in said receiver for said connection.

4. The method according to claim 2, wherein said number of buffers available for storage of data cells received from said transmitter is dynamically adjusted based upon a priority associated with said connection.

5. The method according to claim 1, wherein said number of buffers available and said number of data cells releasable are dynamically adjusted based upon current buffer demands in said receiver for said connection.

6. The method according to claim 1, wherein said number of buffers available and said number of data cells releasable are dynamically adjusted based upon a priority associated with said connection.

7. The method according to claim 1, wherein said number of buffers available and said number of data cells releasable are dynamically adjusted based upon an input to said transmitter and receiver from an external source.

8. The method according to claim 1, wherein said step of dynamically adjusting said number of buffers available to said connection further comprises dynamically adjusting said number of buffers in a first storage location in said transmitter.

9. The method according to claim 1, wherein said steps of generating said first and second counts are performed in said transmitter.

10. The method according to claim 1, wherein said steps of generating said third and fourth counts are performed in said receiver.

11. The method according to claim 1, wherein said step of dynamically adjusting said number of data cells releasable from buffers in said receiver during said first interval further comprises dynamically adjusting said number of data cells in a second storage location in said receiver.

12. The method according to claim 1, wherein said step of storing said number of data cells actually released from buffers in said receiver during said first interval further comprises storing said number of data cells actually released in a third storage location in said receiver.

13. The method according to claim 1, wherein said step of dynamically adjusting a number of buffers available to said connection further comprises dynamically adjusting a maximum number of buffers available to said connection.

14. The method according to claim 1, wherein said step of dynamically adjusting a number of data cells releasable from buffers in said receiver during a first interval further comprises dynamically adjusting a maximum number of data cells releasable from buffers in said receiver during said first interval.

15. A method of sharing a finite number of buffers within a receiver, said receiver being connected to a transmitter via a flow controlled connection, said method comprising the steps of:

dynamically adjusting a number of buffers available to said connection;

generating a first count indicative of the number of data cells transmitted through said connection by said transmitter to said receiver;

generating a second count indicative of data cells currently being transmitted through said connection by said transmitter to said receiver and indicative of data cells not known to be released from a subset of said buffers in said receiver;

generating a third count indicative of the total number of buffers in said receiver presently storing data cells;

generating a fourth count indicative of data cells received in said receiver from said transmitter via said connection;

dynamically adjusting a number of data cells releasable from buffers in said receiver during a first interval; and

storing a number of data cells actually released from buffers in said receiver during said first interval.

16. The method according to claim 15, further comprising the step of:

dynamically adjusting a number of buffers available for storage of data cells received from said transmitter via said connection.

17. The method according to claim 16, wherein said number of buffers available for storage of data cells received from said transmitter is dynamically adjusted based upon current buffer demands in said receiver for said connection.

18. The method according to claim 16, wherein said number of buffers available for storage of data cells received from said transmitter is dynamically adjusted based upon a priority associated with said connection.

19. The method according to claim 15, wherein said number of buffers available and said number of data cells releasable are dynamically adjusted based upon current buffer demands in said receiver for said connection.

20. The method according to claim 15, wherein said number of buffers available and said number of data cells releasable are dynamically adjusted based upon a priority associated with said connection.

21. The method according to claim 15, wherein said number of buffers available and said number of data cells releasable are dynamically adjusted based upon an input to said transmitter and said receiver from an external source.

22. The method according to claim 15, wherein said step of dynamically adjusting said number of buffers available to said connection further comprises dynamically adjusting said number of buffers in a first storage location in said transmitter.

23. The method according to claim 15, wherein said steps of generating said first and second counts are performed in said transmitter.

24. The method according to claim 15, wherein said steps of generating said third and fourth counts are performed in said receiver.

25. The method according to claim 15, wherein said step of dynamically adjusting said number of data cells releasable from buffers in said receiver during said first interval further comprises dynamically adjusting said number of data cells in a second storage location in said receiver.

26. The method according to claim 15, wherein said step of storing said number of data cells actually released from buffers in said receiver during said first interval further comprises storing said number of data cells actually released in a third storage location in said receiver.

27. The method according to claim 16, wherein said step of dynamically adjusting said number of buffers available for storage of data cells received from said transmitter via said connection further comprises dynamically adjusting, in a third storage location within said receiver, said number of buffers available for storage of data cells.

28. The method according to claim 15, wherein said step of dynamically adjusting a number of buffers available to said connection further comprises dynamically adjusting a maximum number of buffers available to said connection.

29. The method according to claim 15, wherein said step of dynamically adjusting a number of data cells releasable from buffers in said receiver during a first interval further comprises dynamically adjusting a maximum number of data cells releasable from buffers in said receiver during said first interval.