Multiplex communications – Communication techniques for information carried in plural... – Adaptive
Reexamination Certificate
1999-03-16
2003-09-30
Olms, Douglas (Department: 2732)
Multiplex communications
Communication techniques for information carried in plural...
Adaptive
C370S395210, C370S395410
Reexamination Certificate
active
06628668
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATIONS
Not Applicable
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH DEVELOPMENT
Not Applicable
BACKGROUND OF THE INVENTION
In many devices and/or systems used to facilitate data communications, resources must be shared between multiple users or requesters. For example, a switching device may be used to support multiple virtual connections which pass through it. As such connections are established, the switch receives requests to reserve sufficient bandwidth within the switch to support the Quality of Service (QOS) parameters associated with each connection. In order to support the largest possible number of connections, the switch must allocate bandwidth in a manner which minimizes any excess bandwidth allocation. In addition, bandwidth must be allocated across multiple connections in a way that avoids undue delay in processing data units for any particular one of the connections.
Additional performance considerations relate to processing of the bandwidth reservation requests. In general, the number of operations necessary to satisfy a given request should be minimized. This becomes especially important when the switch must support large numbers of connections.
In existing systems, significant amounts of excess bandwidth allocation have resulted in unnecessary denials of bandwidth allocation requests. Such systems also failed to allocate bandwidth in a manner which closely matched the delay sensitivity of the specific connections.
Thus, in view of the prior art's shortcomings, there is a need for a bandwidth allocation system in a network switch that accurately matches the amount of bandwidth allocated for a connection to the amount of bandwidth requested. The system should allocate bandwidth such that no undue delays are introduced to traffic on connections through the switch. The system should also service bandwidth allocation requests with a minimum of delay.
SUMMARY OF THE INVENTION
In accordance with principles of the invention, a new system for allocating bandwidth in a communications device is disclosed. The disclosed system receives a bandwidth allocation request, as is received during establishment of a virtual connection, and determines whether the request is associated with a delay sensitive connection type. Examples of delay sensitive connection types include Continuous Bit Rate (CBR) connections, and Real Time Variable Bit Rate (RT-VBR) connections. In the event that the bandwidth allocation request is associated with a delay sensitive connection type, the system selects a bandwidth allocation algorithm from a first set of bandwidth allocation algorithms. If the bandwidth allocation request is not associated with a delay sensitive connection type, then the system selects a bandwidth allocation algorithm from a second set of bandwidth allocation algorithms.
In another aspect of the disclosed system, the size of the bandwidth allocation request is also examined when selecting which bandwidth allocation algorithm to use. The system selects a specific bandwidth allocation algorithm within the first set of algorithms for a delay sensitive connection if the size of the bandwidth allocation request falls within one or more predetermined ranges of values. The system may also round up the size of the bandwidth allocation request to a predetermined value, such as the upper limit of one of the predetermined value ranges, depending on which bandwidth allocation algorithm is selected.
In an illustrative embodiment, the selected bandwidth allocation algorithm reserves slots for the connection associated with the request in a bandwidth allocation table. The bandwidth allocation table is a data structure including a number of slots which represent times at which virtual connections may transmit data units across a switch fabric. For example, one of the bandwidth allocation algorithms in the first set of algorithms reserves slots that are equally spaced in the bandwidth allocation table. Because, in the illustrative embodiment, switch bandwidth is made available to various connections based on the order of the slots in the bandwidth allocation table, equally spaced reserved slots avoid uneven delays between opportunities to forward cells through the switch. To accomplish this even spacing of bandwidth allocation table slots, one of the first set of bandwidth allocation algorithms includes a bandwidth allocation algorithm which reserves a number of slots in the bandwidth allocation table equal to a power of two greater than or equal to the size of the bandwidth allocation request. For example, the next power of two greater than or equal to the size of the bandwidth allocation request may be selected. Then, given a bandwidth allocation table having a total number of slots also equal to a power of two, the reserved slots may be selected to be equidistant from each other.
In order to facilitate management of the bandwidth allocation table, the illustrative embodiment further includes a binary tree representation of the table. Leaves of the binary tree correspond to individual slots in the bandwidth allocation table. Allocation of a number of slots equal to a power of two may be accomplished by identifying a branch of the binary tree having leaves that each correspond to available slots, where the number of leaves in the branch is equal to the selected power of two.
In another aspect of the disclosed system, a bandwidth allocation algorithm is described which reserves sets of slots in the bandwidth allocation table, such that the resulting number of reserved slots is equal to a sum of powers of two. Again, the number of slots reserved is equal to or greater than the size of the bandwidth allocation request. This bandwidth allocation algorithm is generally applicable to bandwidth allocation requests which are not associated with delay sensitive connections.
In another aspect of the disclosed system, a bandwidth allocation algorithm is described which reserves sets of slots in the switch allocation table, such that the resulting number of reserved slots is equal to a power of two multiplied by an integer. As above, the number of reserved slots is equal to or greater than the size of the bandwidth allocation request. This bandwidth allocation algorithm is advantageously applicable to bandwidth allocation requests which are associated with delay sensitive connections.
Also disclosed is a bandwidth allocation algorithm which reserves sets of slots in the switch allocation table, such that the resulting number of reserved slots is equal to a power of two multiplied by a predetermined value and incremented by a remainder value, where the remainder value is equal to or greater than a size of the bandwidth allocation request minus the product of the power of two and the predetermined value. This bandwidth allocation algorithm is applicable to bandwidth allocation requests which are not associated with delay sensitive connections.
Thus there is disclosed a bandwidth allocation system for a network element or device, such as a network switch, that addresses the aforementioned shortcomings of existing systems. The disclosed system accurately matches the amount of bandwidth allocated for a connection to the amount of bandwidth requested. The disclosed system also allocates bandwidth such that undue delays for traffic on connections through the switch are avoided. In addition, the disclosed system is able to service bandwidth allocation requests with a minimum of delay.
REFERENCES:
patent: 5745694 (1998-04-01), Egawa et al.
patent: 5850399 (1998-12-01), Ganmukhi et al.
patent: 5978374 (1999-11-01), Ghaibeh et al.
patent: 5982748 (1999-11-01), Yin et al.
patent: 6046981 (2000-04-01), Ramamurthy et al.
patent: 6175572 (2001-01-01), Kim
patent: 6212163 (2001-04-01), Aida
patent: 6359889 (2002-03-01), Tazaki et al.
patent: 6438134 (2002-08-01), Chow et al.
Affidavit of Thomas A. Manning executed on Aug. 16, 1999 with Exhibits A-H.
Affidavit of Mark Bernasconi executed on Dec. 13, 1999 with Exhibits A-E.
Affidavit of Jerome executed on Dec. 16, 1999 with Exhibi
Hutzli Peter
Manning Thomas A.
Peck David N.
Fujitsu Network Communications, Inc.
Olms Douglas
Sam Phirin
Weingarten Schurgin, Gagnebin & Lebovici LLP
LandOfFree
Crosspoint switch bandwidth allocation management does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Crosspoint switch bandwidth allocation management, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Crosspoint switch bandwidth allocation management will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3068812