US4965798A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus for flexibly allocating bandwidth for a point-to-point, serial, bidirectional communication path
Assignee: EMC Corp
•
Filing: 1989-02-09
•
Granted: 1990-10-23
•
Expires: 2009-02-09
Abstract
Abstract Methods and apparatus are set forth which provide for the allocation of bandwidth for point-to-point, serial, bidirectional communication paths in a digital switching system. Bandwidth allocation is performed at both ends of a path (e.g. T1 line, IML, etc.) and may take place in either direction. Furthermore, according to the preferred embodiment of the invention, the Bandwidth Allocation Facility (BAF) at each end of a given path allocates bandwidth in integer multiples of maximum switching system granularity. The BAF also supports the implementation of user requests for any one of a plurality of allocation and boundry rules. To minimize the probability of contention and out of band signalling between the BAF pair associated with a given path, a front-to-back search mechanism is assigned for one BAF of the pair, while the other BAF utilizes a back-to-front search mechanism. In this way contention occurs only when a path's capacity nears exhaustion while uneven loading (one side of the path versus the other) is accommodated. Further yet, methods and apparatus are set forth which support rapid deallocation of bandwidth and status reporting.
Inventors
- 👤 Asghar D. Mostafa
- 👤 Kirk H. Berry
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 16:39
CPC Classifications
H; H04; H04J; H04J3/00; H04J3/16; H04J3/1682
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
289 words
In a digital data communication system, having a switching granularity of "x" bps, comprising a plurality of point-to-point, serial, bidirectional data paths each having a bandwidth, wherein the bandwidth of at least a first data path is divided into "m" slots, the slots each being subdivided into "n" fragments where the bandwidth of each granularity x, each one of said plurality of data paths being for transporting data within said system in response to a request for bandwidth from at least one of a set of data path users and wherein the system further comprises user interface manager means that stores, identifies and transmits parameters associated with a given user's bandwidth allocation request, and bandwidth allocation control means, coupled to a first end of said first data path and to said user interface manager means, for controlling allocation of data bandwidth to one or more of the m×n fragments of first data path bandwidth, comprising: (a) bit map means comprising m×n bit locations, each bit location corresponding to a different fragment on said first data path wherein each one of said m×n bit locations is used for storing a binary bit which takes a value of ZERO for indicating that its corresponding fragment is available or a value of ONE for indicating that its corresponding fragment is in use and unavailable; (b) allocation means for identifying available fragments on said first data path, in response to a particular data path user's request for bandwidth allocation, as specified by parameters received from said user interface manager means, wherein said allocation means is capable of performing the allocation in accordance with any one of a plurality of predefined rules, each of which define the bandwidth allocation layout request and any constraints.
Claim 2
Dependent Claim
289 words
In a digital data communication system, having a switching granularity of "x" bps, comprising a plurality of point-to-point, serial, bidirectional data paths each having a bandwidth, wherein the bandwidth of at least a first data path is divided into "m" slots, the slots each being subdivided into "n" fragments where the bandwidth of each granularity x, each one of said plurality of data paths being for transporting data within said system in response to a request for bandwidth from at least one of a set of data path users and wherein the system further comprises user interface manager means that stores, identifies and transmits parameters associated with a given user's bandwidth allocation request, and bandwidth allocation control means, coupled to a first end of said first data path and to said user interface manager means, for controlling allocation of data bandwidth to one or more of the m×n fragments of first data path bandwidth, comprising: (a) bit map means comprising m×n bit locations, each bit location corresponding to a different fragment on said first data path wherein each one of said m×n bit locations is used for storing a binary bit which takes a value of ZERO for indicating that its corresponding fragment is available or a value of ONE for indicating that its corresponding fragment is in use and unavailable; (b) allocation means for identifying available fragments on said first data path, in response to a particular data path user's request for bandwidth allocation, as specified by parameters received from said user interface manager means, wherein said allocation means is capable of performing the allocation in accordance with any one of a plurality of predefined rules, each of which define the bandwidth allocation layout request and any constraints.
Claim 3
Dependent Claim
88 words
Apparatus as set forth in claim 1 wherein said allocation means further comprises means for identifying available fragments in accordance with the constraints associated with a given one of said predefined rules, by locating a corresponding ZERO in the bit map means, assigning data bandwidth to the available fragment, and marking the fragment as being in use by recording a ONE in the fragments corresponding bit location in said bit map means, thereby allocating bandwidth in fragment packets that are integer multiples of the maximum switching system granularity.
Claim 4
Dependent Claim
35 words
Apparatus as set forth in claim 2 wherein said allocation means is capable of performing nonrestrictive bandwidth allocation to thereby permit any combination of m×n fragments to be used to fulfill a particular bandwidth request.
Claim 5
Dependent Claim
35 words
Apparatus as set forth in claim 2 wherein said allocation means is capable of performing slot restrictive bandwidth allocation thereby restricting allocation to fulfill a bandwidth request to fragments from one of said m slots.
Claim 6
Dependent Claim
33 words
Apparatus as set forth in claim 2 wherein said allocation means is capable of performing contiguous bandwidth allocation thereby restricting allocation to fulfill a bandwidth request to contiguous fragments without being slot restrictive.
Claim 7
Dependent Claim
39 words
Apparatus as set forth in claim 2 wherein said allocation means is capable of performing contiguous slot restrictive bandwidth allocation thereby restricting allocation to fulfill a bandwidth request to contiguous fragments within the same one of said m slots.
Claim 8
Dependent Claim
29 words
Apparatus as set forth in claim 1 wherein said set of predefined rules includes a default allocation rule in the event no allocation rule is specified by the user.
Claim 9
Dependent Claim
57 words
A digital communication system set forth in claim 1 further comprising deallocation means, coupled to said user interface manager means and responsive to transmitted parameters input therefrom, for designing data bandwidth off said first data path and for marking fragments deallocated as available by recording a ZERO in the corresponding bit location in said bit map means.
Claim 10
Dependent Claim
27 words
Apparatus as set forth in claim 8 wherein said deallocation means is responsive to a unique request ID number to deallocate a block of previously assigned fragments.
Claim 11
Dependent Claim
149 words
A digital communications system as set forth in claim 8 wherein said first data path includes a signalling channel for exchanging procedural information between said bandwidth allocation control means coupled to said first end of said first data path and a second bandwidth allocation control means coupled to the second, opposite end of said first data path, and further wherein each allocation control means is such that: (a) the bit map means is linearly organized, having a first end and a second end opposite to the first end; and (b) in the allocation means, available fragments are identified by the allocation control means coupled to the first end of said first path, by searching from the first end of the bit map means, and by the allocation control means coupled to the second end of said first path, by searching from the second end of the bit map means.
Claim 12
Dependent Claim
61 words
The digital data communication system recited in claim 10 wherein each of the two bandwidth allocation control means, coupled to said first data path, inform the other, via the signalling channel, of fragment allocations made, and each of said two bandwidth allocation control means further include means for updating their respective bit maps according to information received via the signalling channel.
Claim 13
Dependent Claim
40 words
Apparatus as set forth in claim 1 further comprising status reporting means, coupled to said user interface manager and responsive to transmitted parameters input therefrom, for determining and reporting the status of allocation requests to said user interface manager means.
Claim 14
Dependent Claim
27 words
Apparatus as set forth in claim 2 wherein said allocation means is capable of supporting requests for preallocated bandwidth assignments specified by said user interface manager means.
Claim 15
Dependent Claim
32 words
Apparatus as set forth in claim 2 that assigns bandwidth according to a default allocation rule when no predetermined rule is specified by the parameters input from said user interface manager means.
Claim 16
Independent Claim
201 words
A method of allocating bandwidth on each of a plurality of data paths in a digital communication switching system that has a switching granularity of "x" bits per second, wherein each of said data paths has a bandwidth divided into "m" slots, the slots each being subdivided into "n" fragments where n is a function of x, comprising the steps of: (a) allocating bandwidth, via bandwidth allocation control means, in integer multiples of x bits per second in accordance with predefined allocation rules; (b) maintaining a bit map for each end of a given data path wherein each map has at least m×n bit locations, each of said m×n bits corresponding to a different fragment on the path for which the bit maps are being maintained and further wherein the state of each bit indicates whether a particular fragment is available; (c) allocating bandwidth from a given end of said given data path by identifying an available fragment on said line utilizing the bit map being maintained for the given end of the data path; and (d) changing the state of the bit associated with the available fragment being allocated to thereby record that the fragment has been placed into use.
Claim 17
Independent Claim
201 words
A method of allocating bandwidth on each of a plurality of data paths in a digital communication switching system that has a switching granularity of "x" bits per second, wherein each of said data paths has a bandwidth divided into "m" slots, the slots each being subdivided into "n" fragments where n is a function of x, comprising the steps of: (a) allocating bandwidth, via bandwidth allocation control means, in integer multiples of x bits per second in accordance with predefined allocation rules; (b) maintaining a bit map for each end of a given data path wherein each map has at least m×n bit locations, each of said m×n bits corresponding to a different fragment on the path for which the bit maps are being maintained and further wherein the state of each bit indicates whether a particular fragment is available; (c) allocating bandwidth from a given end of said given data path by identifying an available fragment on said line utilizing the bit map being maintained for the given end of the data path; and (d) changing the state of the bit associated with the available fragment being allocated to thereby record that the fragment has been placed into use.
Claim 18
Dependent Claim
35 words
A method as set forth in claim 15 further comprising the step of deallocating previously allocated bandwidth on a given data path by changing the state of the bit corresponding to the fragment being deallocated.
Claim 19
Dependent Claim
122 words
A method as set forth in claim 16 wherein each bit map is linearly organized, having a first end and a second end opposite to said first end, and further wherein the step of allocating bandwidth is performed by first and second bandwidth allocation control means pairs, the first control means of said pair being used to allocate bandwidth from a first end of a given data path and the second control means of said pair being used to allocate bandwidth from a second, opposite end, of said given data path, wherein the first control means allocates bandwidth by identifying an available fragment starting at the first end of the bit map maintained for the first end of said given data path.
Claim 20
Dependent Claim
48 words
A method as set forth in claim 17 wherein said step of allocating bandwidth is further performed by said second control means allocating bandwidth by identifying an available fragment starting at the second end of the bit map maintained for the second end of said given data path.
Claim 21
Dependent Claim
249 words
Apparatus for allocating bandwidth in a digital switching system having a switching granularity of "x" bits per second, wherein said digital switching system further comprises a plurality of point-to-point, serial, bidirectional data paths each having a bandwidth, wherein the bandwidth of at least a first data path is divided into a plurality of slots each of which is further subdivided into a plurality of fragments, wherein the bandwidth of each of said plurality of fragments is chosen as a function of said switching granularity, each one of said plurality of data paths being for transporting data within said system in response to a request for bandwidth from at least one of a set of data path users, comprising: (a) means for inputting a set of bandwidth allocation parameters to bandwidth allocation control means; (b) bandwidth allocation control means, coupled to said means for inputting, for allocating bandwidth as function of said switching granularity ("x" bits per second) in accordance with predetermined allocation rules wherein a particular one of said rules may be specified by a given one of said parameters; and (c) user interface manager means, included in said digital switching system, for storing, identifying and transmitting parameters associated with a given user's bandwidth allocation request, wherein said bandwidth allocation control means is coupled to a first end of said first data path and to said user interface manager means, for controlling allocation of data bandwidth to one or more of said plurality fragments of first data path bandwidth.
Claim 22
Dependent Claim
249 words
Apparatus for allocating bandwidth in a digital switching system having a switching granularity of "x" bits per second, wherein said digital switching system further comprises a plurality of point-to-point, serial, bidirectional data paths each having a bandwidth, wherein the bandwidth of at least a first data path is divided into a plurality of slots each of which is further subdivided into a plurality of fragments, wherein the bandwidth of each of said plurality of fragments is chosen as a function of said switching granularity, each one of said plurality of data paths being for transporting data within said system in response to a request for bandwidth from at least one of a set of data path users, comprising: (a) means for inputting a set of bandwidth allocation parameters to bandwidth allocation control means; (b) bandwidth allocation control means, coupled to said means for inputting, for allocating bandwidth as function of said switching granularity ("x" bits per second) in accordance with predetermined allocation rules wherein a particular one of said rules may be specified by a given one of said parameters; and (c) user interface manager means, included in said digital switching system, for storing, identifying and transmitting parameters associated with a given user's bandwidth allocation request, wherein said bandwidth allocation control means is coupled to a first end of said first data path and to said user interface manager means, for controlling allocation of data bandwidth to one or more of said plurality fragments of first data path bandwidth.
Claim 23
Dependent Claim
106 words
Apparatus as set forth in claim 19 wherein said bandwidth allocation control means further comprises: (a) bit map means for indicating the availability of each of said of plurality of fragments; and (b) allocation means, coupled to said bit map means, for identifying available fragments on said first data path, in response to a particular data path user's request for bandwidth allocation, as specified by parameters received from said user interface manager means, wherein said allocation means is capable of performing the allocation in accordance with any one of a plurality of predefined rules, each of which define the bandwidth allocation layout request and any constraints.
Claim 24
Dependent Claim
50 words
Apparatus as set forth in claim 20 wherein said digital switching system further comprises deallocation means, coupled to said user interface manager means and responsive to transmitted parameters input therefrom, for deassigning data bandwidth off said first data path and for updating said bit map means whenever bandwidth is deallocated.
Claim 25
Dependent Claim
27 words
Apparatus as set forth in claim 21 wherein said deallocation means is responsive to a unique request ID number to deallocate a block of previously assigned fragments.
Claim 26
Dependent Claim
151 words
Apparatus as set forth in claim 21 wherein said first data path of said digital switching system includes a signalling channel for exchanging procedural information between said bandwidth allocation control means coupled to said first end of said first data path and a second bandwidth allocation control means coupled to the second, opposite end of said first data path, and further wherein each allocation control means is such that: (a) the bit map means is linearly organized, having a first end and a second end opposite to the first end; and (b) in the allocation means, available fragments are identified by the allocation control means coupled to the first end of said first path, by searching from the first end of the bit map means, and by the allocation control means coupled to the second end of said first path, by searching from the second end of the bit map means.
Claim 27
Dependent Claim
64 words
Apparatus as set forth in claim 23 wherein each of the two bandwidth allocation control means, coupled to said first data path of said digital switching system, inform the other, via the signalling channel, of fragment allocations made, and each of said two bandwidth allocation control means further include means for updating their respective bit maps according to information received via the signalling channel.
Claim 28
Dependent Claim
20 words
Apparatus as set forth in claim 19 wherein said bandwidth allocation control means is capable of performing nonrestrictive bandwidth allocation.
Claim 29
Dependent Claim
21 words
Apparatus as set forth in claim 19 wherein said bandwidth allocation control means is capable of performing slot restrictive bandwidth allocation.
Claim 30
Dependent Claim
20 words
Apparatus as set forth in claim 19 wherein said bandwidth allocation control means is capable of performing contiguous bandwidth allocation.
Claim 31
Dependent Claim
22 words
Apparatus as set forth in claim 19 wherein said bandwidth allocation control means is capable of performing contiguous slot restrictive bandwidth allocation.
Claim 32
Dependent Claim
28 words
Apparatus as set forth in claim 19 wherein said predetermined allocation rules includes a default allocation rule in the event no allocation rule is specified by the user.
References Cited (Backward Citations)
US4547877A
Cited
US4646290A
Cited
US4658152A
Cited
US4823342A
Cited
US4763319A
Cited
US4852089A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-10-22 | 1994-04-23 | 1994-10-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-10-22 | 1998-04-23 | 1998-10-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-10-22 | 2002-04-23 | 2002-10-23 | $7700.00 | Window Closed / Lapsed |