Allocated and dynamic bandwidth management

• US 5,748,629 A
• Filed: 07/18/1996
• Issued: 05/05/1998
• Est. Priority Date: 07/19/1995
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited, Fujitsu Network Communications Incorporated (Fujitsu Limited)
• Inventors: McClure, Robert B., Hauser, Stephen A., Caldara, Stephen A., Manning, Thomas A., Colsman, Matthias L.
• Primary Examiner(s): Safourek, Benedict V.
• Assistant Examiner(s): Rao, Seema S.
• Application Number:
  US08/683,152
• Time in Patent Office: 656 Days
• Field of Search: 370/250, 370/252, 370/253, 370/351, 370/389, 370/391, 370/392, 370/395, 370/398, 370/399, 370/412, 370/413, 370/414, 370/428, 370/429, 370/465, 370/468, 370/230, 370/235, 340/825.15
• US Class Current: 370/389
• 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

An ATM network switch and method of utilization for adaptively providing integrated services therein is disclosed. In providing such integrated services, if the allocated bandwidth for one connection has been consumed, or if the connection is not entitled to allocated bandwidth, the connection can optionally use dynamic bandwidth arbitration, or a combination of both allocated and dynamic. The switch includes an input port processor, a bandwidth arbiter, and an output port processor. Cells are transmitted from the input to the output, under the control of respective port processors and the bandwidth arbiter. Flow control is implemented on a per-connection basis. Individual queues are then assigned to traffic type groups in order to provide traffic type flow control. Based upon prioritization information associated with the cell at the input, cells are prioritized and transmitted from the output, with each cell maintained in the same order, relative to other cells on a connection, in which it was received.

Claims

1. A data switch providing integrated services to data cells transmitted therethrough, each data cell identified as belonging to one of multiple service classes, said switch comprising:

plural input port processors, each for buffering and enqueuing input data cells and for transmitting said input data cells through said switch using either allocated or dynamic intra-switch bandwidth;

a bandwidth arbiter, in communication with said input port processors, for arbitrating said dynamic intra-switch bandwidth among said input port processors, and for tagging said input data cells as allocated or dynamic intra-switch bandwidth transmitted data cells;

plural output port processors, in communication with said input port processors and said bandwidth arbiter, each for buffering and enqueuing said tagged transmitted data cells, according to said tag and data cell service class information, in a prioritized manner; and

a switch fabric enabling said communication between said input port processors, said bandwidth arbiter, and said output port processors.

2. The switch of claim 1 wherein each of said input processors is further for generating scheduling lists comprised of linked lists of queues of said input data cells, each of said scheduling lists having associated therewith data cells belonging to a common connection.

3. The switch of claim 2 wherein each of said input processors is further maintaining a switch allocation table having plural entries, each of said entries identifying one of said scheduling lists, said switch allocation table enabling the transmission of said input data cells using said allocated intra-switch bandwidth.

4. The switch of claim 3 wherein each of said input processors is further for maintaining plural dynamic bandwidth lists, each relating to a respective one of said output processors and comprising a linked list of at least one scheduling list, said dynamic bandwidth lists enabling transmission of said input data cells using said dynamic intra-switch bandwidth.

5. The switch of claim 4 wherein each of said input processors is further for maintaining a dynamic port list for conveyance to said bandwidth arbiter, said dynamic port list indicating which of said output processors are requested by said dynamic bandwidth list scheduling lists, and at what priority.

6. The switch of claim 5 wherein said bandwidth arbiter is further for identifying which of said output processors is not scheduled for receipt of an input data cell via said allocated intra-switch bandwidth from an input processor, and for matching said output processors not so scheduled with requested output processors on said dynamic port list based upon said priority.

7. The switch of claim 6 wherein said bandwidth arbiter is further for conveying to said input processor an available output processor which corresponds to a request by said input processor.

8. The switch of claim 1 wherein each of said output processors is further for receiving an identification of an input data cell to be transmitted by one of said input processors and for providing an indication to said input processor to inhibit said transmission of said input data cell based upon said identification.

9. The switch of claim 1 wherein each of said output processors is further for maintaining allocated and dynamic list structures for each of said data cells received from said input processors via said allocated and dynamic intra-switch bandwidth, respectively.

10. The switch of claim 9 wherein each of said output processors is further for transmitting data cells associated with said allocated list structures out of said switch before data cells associated with said dynamic list structures.

11. The switch of claim 9 wherein each of said output processors is further for providing said allocated and dynamic list structures for each of said multiple service classes.

12. The switch of claim 11 wherein each of said output processors is further for providing said multiple service class list structures for each of plural priorities.

13. A communications switch providing integrated services to data cells transmitted therethrough, each data cell identified as belonging to one of multiple service classes, said switch having at least one input port in communication with an input communications link, at least one output port in communication with an output communications link, and a switch fabric therebetween, said switch comprising:

an input processor, associated with each of said at least one input ports, for buffering, enqueuing and transmitting said data cells received from said input communications link according to a determination, made by said input processor, of whether allocated or dynamic intra-switch bandwidth may be utilized in transmitting said enqueued data cells across said switch fabric;

a bandwidth arbiter, in communication with said at least one input processor, for arbitrating said dynamic intra-switch bandwidth among said input processors, and for tagging said data cells with a tag indicative of whether a respective data cell has been transmitted across said switch fabric utilizing said allocated or said dynamic intra-switch bandwidth; and

an output processor, associated with each of said at least one output ports, for buffering and enqueuing said data cells transmitted by at least one of said input processors, tagged by said bandwidth arbiter, and received across said switch fabric, said output processor utilizing said bandwidth arbiter tag and data cell service class information in enqueuing said data cells for transmission to said output communications link in a prioritized manner.

14. The switch of claim 13 wherein said input processor is further capable of verifying valid header data format associated with each of said data cells.

15. The switch of claim 13 wherein said input processor is further capable of verifying a valid connection identifier from header data for each of said data cells.

16. The switch of claim 13 wherein said input processor is further capable of analyzing a connection identifier from header data for each of said data cells in associating said data cell with a queue for the respective connection.

17. The switch of claim 13 wherein said input processor enqueues said data cells for a particular connection in a single queue in order of data cell reception from said input communications link.

18. The switch of claim 13 wherein said input processor is further capable of reformatting said data cells received from said input communications link into a switch-internal format.

19. The switch of claim 13 wherein said input processor is further capable of generating scheduling lists comprised of linked lists of queues of said data cells identified as belonging to a common connection.

20. The switch of claim 19 wherein said input processor maintains a respective switch allocation table comprising plural entries, each entry identifying a respective one of said scheduling lists, said switch allocation table enabling transmission of said enqueued data cells through said switch employing said allocated intra-switch bandwidth.

21. The switch of claim 20 wherein said input processor maintains a dynamic bandwidth list for each of said output ports, each said dynamic bandwidth list comprising a linked list of at least one of said scheduling lists, said dynamic bandwidth lists enabling transmission of said enqueued data cells through said switch employing said dynamic intra-switch bandwidth.

22. The switch of claim 21 wherein said input processor maintains a dynamic port list for conveyance to said bandwidth arbiter, said dynamic port list providing an indication to said bandwidth arbiter of which output ports are requested by said scheduling lists associated with said input processor, and at what priority.

23. The switch of claim 22 wherein said bandwidth arbiter is further capable of identifying which of said output ports are not scheduled for receipt of data cells via said allocated intra-switch bandwidth by said input processor, and of matching said output ports not scheduled with said requested output ports on said dynamic port list based upon said priority.

24. The switch of claim 23 wherein said bandwidth arbiter further conveys to said input processor an available output port which matches one of said output ports requested by said input processor.

25. The switch of claim 24 wherein said bandwidth arbiter is further capable of maintaining a history of which input processors were provided with a requested output port in providing a fairness in output port distribution.

26. The switch of claim 13 wherein said bandwidth arbiter is further capable of receiving from said input processor a queue vector which identifies a destination output processor for ones of said data cells to be transmitted through said switch.

27. The switch of claim 13 wherein said input processor identifies, to at least one of said output processors via said switch fabric, a data cell to be transmitted to said at least one output processor, and

said at least one output processor is further capable of identifying, for said data cell to be transmitted, via said switch fabric, said bandwidth arbiter-provided tag and a respective queue for buffering said data cell at said output port.

28. The switch of claim 27 wherein said output processor is further capable of providing a signal to said input processor providing said data cell to be transmitted, via said switch fabric, said signal inhibiting transmission of said data cell until receipt by said input processor of a further signal from said output processor.

29. The switch of claim 13 wherein said output processor is further capable of maintaining list structures for each of data cells received via said allocated and dynamic intra-switch bandwidths, said list structures comprising linked lists of queues having data cells for transmission to said output communications link.

30. The switch of claim 29 wherein each of said queues is restricted, by said output processor, to one entry within said linked list of queues for each of said list structures.

31. The switch of claim 29 wherein said output processor is further capable of transmitting data cells from queues found on said allocated intra-switch bandwidth list structure before transmitting data cells from queues found on said dynamic intra-switch bandwidth list structure.

32. The switch of claim 29 wherein said output processor is further capable of providing said allocated and dynamic intra-switch bandwidth list structures for each of said multiple service classes.

33. The switch of claim 32 wherein said output processor is further capable of providing said multiple service class list structures for each of plural priorities.

34. A method of forwarding a data cell through a communications switch having an input port, an input processor associated with said input port, an output port, an output processor associated with said output port, a switch fabric disposed between said input port and said output port, and a bandwidth arbiter associated with said switch fabric, said method comprising the steps of:

input buffering and enqueuing a data cell received at said input port by said input processor according to whether said data cell is to be forwarded, via said switch fabric, to said output port via allocated or dynamic intra-switch bandwidth;

tagging said buffered and enqueued data cell by said bandwidth arbiter as a data cell to be forwarded over said switch fabric via said allocated or dynamic intra-switch bandwidth;

forwarding said tagged data cell over said switch fabric by said input processor to said output processor; and

output buffering and enqueuing said forwarded data cell, by said output processor at said output port, according to said tag, in a prioritized manner.

35. The method of claim 34 wherein said input buffering and enqueuing step further comprises error checking, by said input processor, a header associated with said data cell.

36. The method of claim 34 wherein said input buffering and enqueuing step further comprises identification, by said input processor, of a connection to which said data cell corresponds from header data associated with said data cell.

37. The method of claim 34 wherein said input buffering and enqueuing step further comprises converting said data cell to a switch-internal data cell format by said input processor.

38. The method of claim 34 wherein said input buffering and enqueuing step further comprises the step of generating, by said input processor, scheduling lists comprised of linked lists of queues identified as belonging to a common connection.

39. The method of claim 38 wherein said input buffering and enqueuing step further comprises the step of maintaining, by said input processor, a switch allocation table comprising plural entries, each entry identifying a respective one of said scheduling lists, said switch allocation table enabling transmission of said enqueued data cell through said switch employing said allocated intra-switch bandwidth.

40. The method of claim 38 wherein said input buffering and enqueuing step further comprises the step of maintaining, by said input processor, a dynamic bandwidth list for said output port, said dynamic bandwidth list comprising a linked list of at least one of said scheduling lists and enabling transmission of said enqueued data cell through said switch employing said dynamic intra-switch bandwidth.

41. The method of claim 40 wherein said input buffering and enqueuing step further comprises the step of maintaining a dynamic port list, by said input processor, said dynamic port list to provide an indication to said bandwidth arbiter of whether said output port is requested by said scheduling lists associated with said input processor, and at what priority.

42. The method of claim 41 wherein said tagging step further comprises the step of identifying, by said bandwidth arbiter, whether said output port is scheduled for receipt of said data cell via said allocated intra-switch bandwidth by said input processor during a first interval, and of matching, by said bandwidth arbiter, said output port not scheduled during said first interval with said output port request on said dynamic port list based upon said priority.

43. The method of claim 42 wherein said step of matching further comprises the step of conveying, by said bandwidth arbiter, said matched output port to said requesting input processor.

44. The method of claim 42 wherein said step of matching further comprises the step of maintaining a history of matched output port requests.

45. The method of claim 34 wherein said step of tagging further comprises the step of receiving, by said bandwidth arbiter, a queue vector, from said input processor, for identifying a destination output processor for said enqueued data cell to be transmitted through said switch.

46. The method of claim 34 wherein said step of forwarding said tagged data cell further comprises the step of providing, by said output processor, a signal to said input processor inhibiting said forwarding of said tagged data cell until said output processor provides a second signal to said input processor.

47. The method of claim 34 wherein said step of output buffering and enqueuing further comprises the step of maintaining, by said output processor, list structures for each of data cells received from said input processor via said allocated and dynamic intra-switch bandwidth, said list structures comprising linked lists of queues each having data cells for transmission from said output port.

48. The method of claim 47 wherein said step of maintaining further comprises entering, by said output processor, a queue, having a data cell for transmission from said output switch, on said linked list of queues only once for each of said list structures.

49. The method of claim 47 wherein said step of maintaining further comprises transmitting data cells from queues found on said allocated intra-switch bandwidth list structure before transmitting data cells from queues found on said dynamic intra-switch bandwidth list structure.

50. The method of claim 47 wherein said data cell is associated with one of plural service classes and said step of maintaining further comprises providing plural allocated and dynamic intra-switch bandwidth list structures for each of said multiple service classes.

51. The method of claim 50 wherein said step of maintaining further comprises providing said multiple service class list structures for each of plural priorities.