US5838663A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for admission control and routing by allocating network resources in network nodes
Assignee: Nokia of America Corp
•
Filing: 1997-04-25
•
Granted: 1998-11-17
•
Expires: 2017-04-25
Abstract
Abstract A method regulates the admission control of, and requests for routing of, virtual circuits in a network by determining network resource requirements for the virtual circuits. In particular, the network resource requirements are based on a set of parameters used to control the flow of information from a communications device onto the virtual circuit. The requirements for network resources typically include buffer space requirements in network nodes and bandwidth requirements in network links, and the parameter used to control the flow of information are those associated with an access regulator. The network resource determination is made for the case where lossless performance in the network is required and in the case where statistical multiplexing with limited loss is allowed. Both constant bit rate and variable bit rate information is considered.
Inventors
- 👤 Anwar Elwalid
- 👤 Debasis Mitra
- 👤 Robert H. Wentworth
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 04:02
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/70; H04L47/82; H04L47/822; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L47/10; H04L47/15; H04L47/78; H04L47/783; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04Q3/00; H04Q3/0016; H04Q3/0062; H04L2012/5619; H04L2012/562; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5678; H04L2012/5684; H04Q2213/00; H04Q2213/13526; H04Q2213/13531; H04Q2213/13541
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
190 words
A method comprising the steps of: receiving a signal representing a request for a virtual circuit for conveying data from a communication device, the requested virtual circuit to be routed through a node connected to a link, said node comprising a buffer of size B and said link being characterized by a capacity C, wherein said data arrives at said node at a rate characterized by a set of parameters, said set of parameters including a long term average rate r, a maximum burst size B T and a peak rate P; determining effective bandwidth and buffer space requirements e 0 and b 0 from said set of parameters, wherein a ratio of said effective buffer space requirement b 0 to said buffer size B is substantially equal to a ratio of said effective bandwidth requirement e 0 to said link bandwidth capacity C, said effective bandwidth requirement e 0 satisfying the expression: ##EQU77## admitting said virtual circuit request if said determined bandwidth and buffer space requirements e 0 and b 0 are less than available buffer memory space in said buffer and available link bandwidth capacity in said link.
Claim 2
Independent Claim
190 words
A method comprising the steps of: receiving a signal representing a request for a virtual circuit for conveying data from a communication device, the requested virtual circuit to be routed through a node connected to a link, said node comprising a buffer of size B and said link being characterized by a capacity C, wherein said data arrives at said node at a rate characterized by a set of parameters, said set of parameters including a long term average rate r, a maximum burst size B T and a peak rate P; determining effective bandwidth and buffer space requirements e 0 and b 0 from said set of parameters, wherein a ratio of said effective buffer space requirement b 0 to said buffer size B is substantially equal to a ratio of said effective bandwidth requirement e 0 to said link bandwidth capacity C, said effective bandwidth requirement e 0 satisfying the expression: ##EQU77## admitting said virtual circuit request if said determined bandwidth and buffer space requirements e 0 and b 0 are less than available buffer memory space in said buffer and available link bandwidth capacity in said link.
Claim 3
Dependent Claim
53 words
The method of claim 1 wherein a set of i admitted virtual circuits, having respective bandwidth requirements e i are already routed through said node and wherein the step of admitting comprises the step of: routing an i+1 th requested virtual circuit through said node with respective bandwidth requirements e i+1 if ##EQU78##
Claim 4
Dependent Claim
23 words
The method of claim 1 wherein said set of parameters characterize a function for controlling said rate of data from said communication device.
Claim 5
Dependent Claim
14 words
The method of claim 3 wherein said function is performed by an access regulator.
Claim 6
Dependent Claim
14 words
The method of claim 4 wherein said access regulator is a leaky bucket regulator.
Claim 7
Dependent Claim
25 words
The method of claim 1 further comprising the step of allocating said effective bandwidth requirement e 0 in said link for said admitted virtual circuit.
Claim 8
Dependent Claim
26 words
The method of claim 1 further comprising the step of allocating said effective buffer space requirement b 0 in said buffer for said admitted virtual circuit.
Claim 9
Dependent Claim
54 words
The method of claim 1 wherein a set of i admitted virtual circuits, having respective buffer requirements b i are already routed through said node and wherein the step of admitting comprises the step of: routing an i+1 th requested virtual circuit through said node with respective buffer size requirement b i+1 if ##EQU79##
Claim 10
Independent Claim
182 words
A method comprising the steps of: receiving a signal representing a request for admission of a virtual circuit in a network for conveying data from a first communication device to a second communication device, the requested virtual circuit to be routed through an access regulator and at least one node connected to a corresponding link of said network, wherein data transmission characteristics of said access regulator are represented by a set of parameters, and wherein said node includes a buffer of size B, and said link is characterized by a bandwidth capacity C; determining effective bandwidth and buffer space requirements e 0 and b 0 from said set of parameters, wherein a ratio of said effective buffer space requirement b 0 to said buffer size B is substantially equal to a ratio of said effective bandwidth requirement e 0 to said link bandwidth capacity C: and admitting said virtual circuit request if said determined bandwidth and buffer space requirements e 0 and b 0 are less than available buffer memory space in said buffer and available link bandwidth capacity in said link.
Claim 11
Independent Claim
182 words
A method comprising the steps of: receiving a signal representing a request for admission of a virtual circuit in a network for conveying data from a first communication device to a second communication device, the requested virtual circuit to be routed through an access regulator and at least one node connected to a corresponding link of said network, wherein data transmission characteristics of said access regulator are represented by a set of parameters, and wherein said node includes a buffer of size B, and said link is characterized by a bandwidth capacity C; determining effective bandwidth and buffer space requirements e 0 and b 0 from said set of parameters, wherein a ratio of said effective buffer space requirement b 0 to said buffer size B is substantially equal to a ratio of said effective bandwidth requirement e 0 to said link bandwidth capacity C: and admitting said virtual circuit request if said determined bandwidth and buffer space requirements e 0 and b 0 are less than available buffer memory space in said buffer and available link bandwidth capacity in said link.
Claim 12
Dependent Claim
49 words
The method of claim 9 wherein said set of parameters representing said transmission characteristics of said access regulator comprise a long term average rate r, a maximum burst size B T , and a peak rate P and wherein said effective bandwidth requirement e 0 satisfies the expression: ##EQU80##
Claim 13
Dependent Claim
14 words
The method of claim 9 wherein said access regulator is a leaky bucket regulator.
Claim 14
Dependent Claim
25 words
The method of claim 9 further comprising the step of allocating said effective bandwidth requirement e 0 in said link for said admitted virtual circuit.
Claim 15
Dependent Claim
54 words
The method of claim 12 wherein a set of i admitted virtual circuits, having respective bandwidth requirements e i are already routed through said node and wherein the step of admitting comprises the step of: routing an i+1 th requested virtual circuit through said node with respective associated bandwidth requirement e i+1 if ##EQU81##
Claim 16
Dependent Claim
26 words
The method of claim 9 further comprising the step of allocating said effective buffer space requirement b 0 in said node for said admitted virtual circuit.
Claim 17
Dependent Claim
56 words
The method of claim 14 wherein a set of i admitted virtual circuits, having respective buffer space requirements b I are already routed through said node and wherein the step of admitting comprises the step of: routing an i+1 th requested virtual circuit through said node with respective associated buffer space requirement b i+1 if ##EQU82##
Claim 18
Independent Claim
232 words
A method comprising the steps of: a) receiving a signal representing a request for a admission of a virtual circuit for conveying data from a first communication device to a second communication device, the requested virtual circuit to be routed through an access regulator having data transmission characteristics represented by a set of parameters, b) selecting a set of N potential paths for said requested virtual circuit, the n th potential path comprising a set of J n nodes wherein the j th node in said set of J n nodes comprises a buffer of size B jn and wherein the j th node is connected to a link of capacity C jn , and c) determining effective bandwidth and buffer space requirements e 0in and b 0in from said set of parameters for nodes and links forming at least one of said potential paths, wherein a ratio of said effective buffer space requirement b 0in to said buffer size B in is substantially equal to a ratio of said effective bandwidth requirement e 0in to said link bandwidth capacity C in ; and d) admitting said virtual circuit request to a particular one of said potential paths if said determined bandwidth and buffer space requirements e 0in and b 0in are less than available buffer memory space in said node buffers and available bandwidth capacity in links forming said particular path.
Claim 19
Independent Claim
232 words
A method comprising the steps of: a) receiving a signal representing a request for a admission of a virtual circuit for conveying data from a first communication device to a second communication device, the requested virtual circuit to be routed through an access regulator having data transmission characteristics represented by a set of parameters, b) selecting a set of N potential paths for said requested virtual circuit, the n th potential path comprising a set of J n nodes wherein the j th node in said set of J n nodes comprises a buffer of size B jn and wherein the j th node is connected to a link of capacity C jn , and c) determining effective bandwidth and buffer space requirements e 0in and b 0in from said set of parameters for nodes and links forming at least one of said potential paths, wherein a ratio of said effective buffer space requirement b 0in to said buffer size B in is substantially equal to a ratio of said effective bandwidth requirement e 0in to said link bandwidth capacity C in ; and d) admitting said virtual circuit request to a particular one of said potential paths if said determined bandwidth and buffer space requirements e 0in and b 0in are less than available buffer memory space in said node buffers and available bandwidth capacity in links forming said particular path.
Claim 20
Dependent Claim
30 words
The method of claim 16 further comprising the step of allocating said effective bandwidth requirement e 0in in said respective links forming said particular path for said admitted virtual circuit.
Claim 21
Dependent Claim
96 words
The method of claim 17 wherein said j th node in said particular path for said admitted virtual circuit has a set of I jn virtual circuits already routed through said j th node and wherein the i th admitted virtual circuit in said set of I jn virtual circuits through said j th node has been allocated bandwidth e i ,jn and wherein the step of admitting comprises the step of: choosing said particular n th path as a path in a set of viable paths if for the n th path: ##EQU83## is satisfied.
Claim 22
Dependent Claim
36 words
The method of claim 16 further comprising the step of allocating said effective buffer space requirement b 0in in said respective buffers B jn of said nodes in said particular path for said admitted virtual circuit.
Claim 23
Dependent Claim
100 words
The method of claim 19 wherein said j th node in said particular path for said admitted virtual circuit has a set of I jn admitted virtual circuits already routed through said j th node and wherein the i th admitted virtualcircuit in said set of I jn virtual circuits through said j th node has been allocated buffer space requirement b i ,jn and wherein the step of admitting comprises the step of: choosing said particular n th potential path as a path in said set of viable paths if for the n th potential path: ##EQU84## is satisfied.
Claim 24
Dependent Claim
206 words
In a network comprising a node, said node connected to a link of capacity C and to a set of access regulators, wherein each access regulator is characterized by a set of parameters, wherein each access regulator has an associated virtual circuit routed through it and through said node and wherein identical sets of parameters characterize a class associated with the identical sets of parameters, a method comprising the steps of: receiving a signal representing a request for a virtual circuit, the virtual circuit to be routed through a particular access regulator characterized by a particular set of parameters and through said node, the set of parameters characterizing a particular class, determining an effective bandwidth for each class through said node, at said node determining a maximum number of requests for virtual circuits of said particular class that can be routed through said node for a given probability of loss, allocating to said request a bandwidth requirement as a function of said capacity C and said maximum number, and admitting said request if the sum of the product of the effective bandwidths for each class and the number of virtual circuits associated with each class is less than said capacity C minus said allocated bandwidth requirement.
Claim 25
Dependent Claim
206 words
In a network comprising a node, said node connected to a link of capacity C and to a set of access regulators, wherein each access regulator is characterized by a set of parameters, wherein each access regulator has an associated virtual circuit routed through it and through said node and wherein identical sets of parameters characterize a class associated with the identical sets of parameters, a method comprising the steps of: receiving a signal representing a request for a virtual circuit, the virtual circuit to be routed through a particular access regulator characterized by a particular set of parameters and through said node, the set of parameters characterizing a particular class, determining an effective bandwidth for each class through said node, at said node determining a maximum number of requests for virtual circuits of said particular class that can be routed through said node for a given probability of loss, allocating to said request a bandwidth requirement as a function of said capacity C and said maximum number, and admitting said request if the sum of the product of the effective bandwidths for each class and the number of virtual circuits associated with each class is less than said capacity C minus said allocated bandwidth requirement.
Claim 26
Independent Claim
209 words
A method comprising the steps of: receiving a signal representing a request for admission of a virtual circuit for conveying data from a first communication device to a second communication device, the requested virtual circuit to be routed through an access regulator and at least one node connected to a corresponding link, wherein data transmission characteristics of said access regulator are represented by a set of parameters, and wherein said node includes a buffer of size B, and said link is characterized by a bandwidth capacity C; determining effective bandwidth and buffer space requirements e 0 and b 0 from said set of parameters, wherein a ratio of said effective buffer space requirement b 0 to said buffer size B is substantially equal to a ratio of said effective bandwidth requirement e 0 to said link bandwidth capacity C; determining a required bandwidth and buffer space allotments e and b based on said effective buffer space and bandwidth requirement b 0 and e 0 an acceptable data loss probability L; and admitting said virtual circuit request if said determined required bandwidth and buffer space allotments e and b are less than or equal to available buffer memory space in said buffer and available link bandwidth capacity in said link.
Claim 27
Independent Claim
209 words
A method comprising the steps of: receiving a signal representing a request for admission of a virtual circuit for conveying data from a first communication device to a second communication device, the requested virtual circuit to be routed through an access regulator and at least one node connected to a corresponding link, wherein data transmission characteristics of said access regulator are represented by a set of parameters, and wherein said node includes a buffer of size B, and said link is characterized by a bandwidth capacity C; determining effective bandwidth and buffer space requirements e 0 and b 0 from said set of parameters, wherein a ratio of said effective buffer space requirement b 0 to said buffer size B is substantially equal to a ratio of said effective bandwidth requirement e 0 to said link bandwidth capacity C; determining a required bandwidth and buffer space allotments e and b based on said effective buffer space and bandwidth requirement b 0 and e 0 an acceptable data loss probability L; and admitting said virtual circuit request if said determined required bandwidth and buffer space allotments e and b are less than or equal to available buffer memory space in said buffer and available link bandwidth capacity in said link.
Claim 28
Dependent Claim
45 words
The method of claim 22 wherein said step of determining said required bandwidth allotment e determines a plurality of allotments e j based on a corresponding plurality of effective bandwidth e 0 ,j for respective classes j=1, . . . , J of LBR parameters.
Claim 29
Dependent Claim
67 words
The method of claim 23 wherein said at least one required bandwidth allotment e j determination for a respective class j of LBR parameters satisfies the expression e j =C/ Kmaxj and wherein maximum number of connections K maxj for the class j further satisfies the requirement of the probability of K maxj ·e 0 >C is less than or equal to said acceptable loss probability L.
Claim 30
Dependent Claim
35 words
The method of claim 24 wherein the value K maxj satisfies the expression ##EQU85## wherein a=(C/e 0 )/K and w=r/e 0 and wherein r is a long term average rate transmitted by said access regulator.
Claim 31
Dependent Claim
46 words
The method of claim 24 wherein said step of determining said bandwidth allotments e j is performed for a plurality of LBR parameter classes j-1, . . . , J and wherein the respective values K maxj for the classes j also satisfies the expression: ##EQU86##
Claim 32
Dependent Claim
36 words
The method of claim 26 wherein at least one class j is non-statistically multiplexible and wherein said corresponding bandwidth allotment e j for that class is set to said corresponding effective bandwidth allotment e 0j .
Claim 33
Dependent Claim
53 words
The method of claim 27 wherein a class is non-statistically multiplexible if the link bandwidth capacity C is than a critical capacity C c satisfying the expression: ##EQU87## wherein w j =r/e 0j and wherein r is a long term average rate transmitted by said access regulator having LBR parameters of class j.
Claim 34
Dependent Claim
121 words
The method of claim 23 wherein said plurality of LBR parameter classes include at least one statistically multiplexible class and at least on non-statistically multiplexible class, the method further comprising: determining a maximum permissible number of connections K maxj for said classes j=1, . . . ,J; determining a breakpoint K s ,j for j=1, . . . , J that satisfy the expressions: ##EQU88## wherein w j =r/e 0j and wherein r is a long term average rate transmitted by said access regulator having LBR parameters of class j; and determining the bandwidth allotments e j for said classes j=1, . . . ,J based on said determined maximum permissible number of connections K maxj and breakpoint K sj .
Claim 35
Dependent Claim
49 words
The method of claim 22 wherein said set of parameters representing said transmission characteristics of said access regulator comprise a long term average rate r, a maximum burst size B T , and a peak rate P and wherein said effective bandwidth requirement e 0 satisfies the expression: ##EQU89##
References Cited (Backward Citations)
US5132966A
Cited
US5179556A
Cited
US5233604A
Cited
US5289462A
Cited
US5311513A
Cited
US5357507A
Cited
US5359593A
Cited
US5426635A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-16 | 2002-05-18 | 2002-11-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-16 | 2006-05-18 | 2006-11-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-16 | 2010-05-18 | 2010-11-17 | $7700.00 | Window Closed / Lapsed |