Crosspoint switch bandwidth allocation management

• US 6,628,668 B1
• Filed: 03/16/1999
• Issued: 09/30/2003
• Est. Priority Date: 03/16/1999
• Status: Expired due to Fees

• Current Assignee: Fujitsu Network Communications Incorporated (Fujitsu Limited)
• Original Assignee: Fujitsu Network Communications Incorporated (Fujitsu Limited)
• Inventors: Manning, Thomas A., Hutzli, Peter, Peck, David N.
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): Sam, Phirin
• Application Number:
  US09/270,950
• Time in Patent Office: 1,659 Days
• Field of Search: 370/229-235, 370/252, 370/253, 370/395.2, 370/395.21, 370/395.4, 370/395.41, 370/395.42, 370/395.43, 370/412, 370/413, 370/415, 370/417, 370/468, 370/395.61, 709/103, 709/104, 709/225, 709/226, 709/228
• US Class Current: 370/468
• 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/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/801 Real time traffic
• CPC Class Codes: H04L 47/805 QOS or priority aware

Abstract

A system for allocating bandwidth in a network element. The system determines whether a bandwidth allocation request is associated with a delay sensitive connection type. If so, the system selects a bandwidth allocation algorithm from a first set of bandwidth allocation algorithms. Otherwise, the system selects a bandwidth allocation algorithm from a second set of bandwidth allocation algorithms. The size of the bandwidth allocation request may be examined when selecting which bandwidth allocation algorithm to use. The system may round up the size of the bandwidth allocation request to a predetermined value. The selected bandwidth allocation algorithm may reserve slots in a bandwidth allocation table. Reserved slots that are equally spaced in the bandwidth allocation table avoid undue delays in servicing an associated connection. A binary tree representation of the table is described, wherein leaves of the binary tree correspond to individual table slots. Specific bandwidth allocation algorithms are described which are advantageously applicable when allocating bandwidth to delay sensitive or relatively delay insensitive connection types.

Claims

1. A method for allocating bandwidth in a switch, comprising:

determining whether a bandwidth allocation request is associated with a delay sensitive connection type;

selecting, in the event that said bandwidth allocation request is associated with said delay sensitive connection type, at least one of a first set of bandwidth allocation algorithms;

selecting, in the event that said bandwidth allocation request is not associated with said delay sensitive connection type, at least one of a second set of bandwidth allocation algorithms; and

responsive to a selected bandwidth allocation algorithm, reserving slots for a connection associated with said allocation request in a bandwidth allocation table, wherein said bandwidth allocation table includes a plurality of slots, each of said slots representing a time at which a predetermined number of data units may be transmitted across a switch fabric, wherein said predetermined number of data units is the same for each of said slots in said bandwidth allocation table, and wherein said at least one of said first set of bandwidth allocation algorithms allocates slots in said bandwidth allocation table that are spaced substantially equally from each other within said bandwidth allocation table.

2. The method of claim 1 wherein said delay sensitive connection type is a continuous bit rate connection type.

3. The method of claim 1 wherein said delay sensitive connection type is a real time variable bit rate connection type.

4. The method of claim 1, wherein said selecting at least one of said first set of bandwidth allocation algorithms further comprises selecting a first one of said first set of bandwidth allocation algorithms in the event that a size of said bandwidth allocation request falls within a first range.

5. The method of claim 4, wherein said selecting at least one of said first set of bandwidth allocation algorithms further comprises selecting a second one of said first set of bandwidth allocation algorithms in the event that said size of said bandwidth allocation request falls within a second range.

8. The method of claim 1, wherein said selecting at least one of a second set of bandwidth allocation algorithms further comprises selecting a first one of said second set of bandwidth allocation algorithms in the event that a size of said bandwidth allocation request falls within a first range.

9. The method of claim 8, wherein said selecting at least one of said second set of bandwidth allocation algorithms further comprises selecting a second one of said second set of bandwidth allocation algorithms in the event that said size of said bandwidth allocation request falls within a second range.

10. The method of claim 1, wherein said at least one of said first set of bandwidth allocation algorithms allocates slots in a bandwidth allocation table, wherein the allocated slots are spaced substantially equally from each other.

6. A method for allocating bandwidth in a switch, comprising:

determining whether a bandwidth allocation request is associated with a delay sensitive connection type;

selecting, in the event that said bandwidth allocation request is associated with said delay sensitive connection type, at least one of a first set of bandwidth allocation algorithms;

selecting, in the event that said bandwidth allocation request is not associated with said delay sensitive connection type, at least one of a second set of bandwidth allocation algorithms;

wherein said selecting at least one of said first set of bandwidth allocation algorithms further comprises selecting a first one of said first set of bandwidth allocation algorithms in the event that a size of said bandwidth allocation request falls within a first range; and

further comprising rounding said size of said bandwidth allocation request up to a predetermined value responsive to said selecting said first one of said first set of bandwidth allocation algorithms.

7. The method of claim 6, wherein said predetermined value is an upper limit of said first range.

11. A method for allocating bandwidth in a switch, comprising:

determining whether a bandwidth allocation request is associated with a delay sensitive connection type;

selecting, in the event that said bandwidth allocation request is associated with said delay sensitive connection type, at least one of a first set of bandwidth allocation algorithms;

selecting, in the event that said bandwidth allocation request is not associated with said delay sensitive connection type, at least one of a second set of bandwidth allocation algorithms; and

wherein said at least one of said first set of bandwidth allocation algorithms reserves a number of said slots in said bandwidth allocation table equal to a power of two greater than a size of said bandwidth allocation request.

12. The method of claim 11, wherein said power of two greater than or equal to said size of said bandwidth allocation request is a next power of two greater than said size of said bandwidth allocation request.

13. The method of claim 11, wherein each of said plurality of slots in said bandwidth allocation table further represents an opportunity to forward said at least one data unit from an inbound port to an outbound port of said switch.

14. The method of claim 13, further comprising a binary tree representation of said plurality of slots in said bandwidth allocation table, wherein leaves of said binary tree correspond to individual slots of said bandwidth allocation table.

15. The method of claim 14, wherein said allocation of said number of slots equal to said power of two greater than said size of said bandwidth allocation request includes identifying a branch of said binary tree having a number of leaves corresponding to available slots, said number of leaves equal to said power of two.

16. A method for allocating bandwidth in a switch, comprising:

determining whether a bandwidth allocation request is associated with a delay sensitive connection type;

selecting, in the event that said bandwidth allocation request is associated with said delay sensitive connection type, at least one of a first set of bandwidth allocation algorithms;

selecting, in the event that said bandwidth allocation request is not associated with said delay sensitive connection type, at least one of a second set of bandwidth allocation algorithms; and

wherein said at least one of said first set of bandwidth allocation algorithms allocates a number of slots in a bandwidth allocation table equal to a power of two multiplied by an integer, wherein said number of slots is greater than or equal to a size of said bandwidth allocation request.

17. A method for allocating bandwidth in a switch, comprising:

determining whether a bandwidth allocation request is associated with a delay sensitive connection type;

selecting, in the event that said bandwidth allocation request is associated with said delay sensitive connection type, at least one of a first set of bandwidth allocation algorithms;

selecting, in the event that said bandwidth allocation request is not associated with said delay sensitive connection type, at least one of a second set of bandwidth allocation algorithms, and

wherein said at least one of said second set of bandwidth allocation algorithms allocates a number of said slots in said bandwidth allocation table equal to a sum of powers of two, wherein said number of slots is equal to or greater than a size of said bandwidth allocation request.

18. The method of claim 17, wherein each of said number of slots further represents an opportunity to forward a data unit from an inbound port to an outbound port of said switch.

19. The method of claim 18, further comprising a binary tree representation of said slots in said bandwidth allocation table, wherein leaves of said binary tree correspond to individual slots of said bandwidth allocation table.

20. The method of claim 19, wherein said allocation of said number of slots equal to said sum of powers of two includes identifying branches of said binary tree having numbers of leaves corresponding to available slots, said number of leaves equal to each power of two within said sum of powers of two.

21. A method for allocating bandwidth in a switch, comprising:

determining whether a bandwidth allocation request is associated with a delay sensitive connection type;

selecting, in the event that said bandwidth allocation request is associated with said delay sensitive connection type, at least one of a first set of bandwidth allocation algorithms;

selecting, in the event that said bandwidth allocation request is not associated with said delay sensitive connection type, at least one of a second set of bandwidth allocation algorithms, and

wherein said at least one of said second set of bandwidth allocation algorithms allocates a number of said slots in said bandwidth allocation table equal to a power of two multiplied by an integer and incremented by a remainder value, wherein said remainder value is equal to a size of said bandwidth allocation request minus said power of two multiplied by said integer.

22. A method for allocating bandwidth in a switch, comprising:

determining whether a bandwidth allocation request is associated with a delay sensitive connection type;

selecting, in the event that said bandwidth allocation request is associated with said delay sensitive connection type, at least one of a first set of bandwidth allocation algorithms;

selecting, in the event that said bandwidth allocation request is not associated with said delay sensitive connection type, at least one of a second set of bandwidth allocation algorithms, and

wherein said at least one of said first set of bandwidth allocation algorithms allocates a number of said slots in said bandwidth allocation table equal to a sum of powers of two, wherein said number of slots is equal to or greater than a size of said bandwidth allocation request.

23. A method for allocating bandwidth in a switch, comprising:

determining whether a bandwidth allocation request is associated with a delay sensitive connection type;

selecting, in the event that said bandwidth allocation request is associated with said delay sensitive connection type, at least one of a first set of bandwidth allocation algorithms;

selecting, in the event that said bandwidth allocation request is not associated with said delay sensitive connection type, at least one of a second set of bandwidth allocation algorithms; and

wherein said at least one of said first set of bandwidth allocation algorithms reserves a number of a plurality of slots in a bandwidth allocation table equal to a power of two equal to a size of said bandwidth allocation request.

24. The method of claim 23, further comprising a binary tree representation of said slots in said bandwidth allocation table, wherein leaves of said binary tree correspond to individual slots of said bandwidth allocation table.

25. The method of claim 24, wherein said allocation of said number of slots equal to said power of two equal to said size of said bandwidth allocation request includes identifying a branch of said binary tree having a number of leaves corresponding to available slots, said number of leaves equal to said power of two.