EP0674459A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
A method of on-line permanent virtual circuit routing
Assignee: AT&T Inc
•
Filing: 1995-03-16
•
Granted: —
•
Expires: 2015-03-16
Abstract
Abstract A method of on-line routing of permanent virtual circuits is disclosed. The method uses an exponential cost function based on the network state and virtual circuit parameters to determine paths for the virtual circuits without scaling. The method may also advantageously use information available when multiple virtual circuits are requested to determine paths for the virtual circuits. Additionally, the method allows the routing selection to be refined so that the total cost of routing all the virtual circuits is reduced.
Inventors
- 👤 Rainer Gawlick
- 👤 Charles Robert Kalmanek, Jr.
- 👤 Kajamalai Gopalaswamy Ramakrishnan
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-24 13:39
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/02; H04L45/10; H04L49/00; H04L49/25; H04L49/256; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
151 words
A method of routing requests for permanent virtual circuits in a network having resources, said network characterized by a network state at least reflecting an allocated amount of a predetermined network resource, said method comprising the steps of: receiving a set of requests, wherein each request in said set of requests is a request to route a permanent virtual circuit on a path and wherein each request is specified by one or more parameters; and for each request: routing the request on a selected path through said network according to an exponential cost function, wherein said selected path satisfies said parameters specifying the request, wherein said exponential function is a function of the network state and of one or more of said parameters specifying the request and wherein said exponential function includes a term having an exponent, said exponent including said allocated amount of said predetermined network resource in unscaled form.
Claim 2
Independent Claim
136 words
A method of routing requests for permanent virtual circuits in a network having resources, said network characterized by a network state reflecting an allocated amount of a predetermined network resource, said method comprising the steps of: receiving a set of requests, wherein each request in said set of requests is a request to route a permanent virtual circuit on a path and wherein each request is specified by one or more parameters; and routing each request on a selected path through said network according to an exponential cost function, wherein said exponential function is a function of the network state and of one or more of said parameters specifying each request and wherein said exponential function includes a term having an exponent, said exponent including said allocated amount of said predetermined network resource in unscaled form.
Claim 3
Independent Claim
72 words
The method of any of the preceding claims further comprising the steps of: selecting an alternative path to one of said selected paths, determining the value of a second function using said alternative path, and determining the value of the second function using said selected path, and if said alternative path improves the value of said second function relative to said selected path, then replacing said selected path with said alternative path.
Claim 4
Dependent Claim
36 words
The method of claim 3 further comprising the step of: repeating the steps of selecting an alternative path, determining values for the second function and replacing until selecting no alternative path will improve the second function.
Claim 5
Dependent Claim
27 words
The method of claim 3 or claim 4 wherein said second function is a function of the network state and of one or more of said parameters.
Claim 6
Independent Claim
46 words
The method of any of the preceding claims further comprising the step of establishing the requests in said set of requests in an order according to one or more of said parameters prior to the routing step, the routing step routing said requests in said order.
Claim 7
Independent Claim
127 words
A method of routing a request for a permanent virtual circuit on a path in a network having resources, wherein said request is specified by one or more parameters and wherein said network is characterized by a network state reflecting an allocated amount of a predetermined network resource, said method comprising the steps of: routing said request on a selected path through said network according to an exponential cost function, wherein said selected path satisfies said parameters specifying said request, wherein said exponential function is a function of the network state and of one or more of said parameters specifying said request and wherein said exponential function includes a term having an exponent, said exponent including said allocated amount of said predetermined network resource in unscaled form.
Claim 8
Independent Claim
22 words
The method of any of the preceding claims further comprising the step of updating said network state to reflect said selected path.
Claim 9
Independent Claim
28 words
The method of any of the preceding claims wherein the Hessian of said exponential function is positive semi-definite and wherein the gradient of said exponential function is non-negative.
Claim 10
Independent Claim
23 words
The method of any of the preceding claims wherein the routing step is carried out based on complete information about said network state.
Claim 11
Independent Claim
24 words
The method of any of claims 1 to 9 wherein the routing step is carried out based on incomplete information about said network state.
Claim 12
Independent Claim
36 words
The method of any of the preceding claims wherein said network comprises a set of links and wherein each selected path through said network is specified by one or more links in said set of links.
Claim 13
Dependent Claim
17 words
The method of claim 12 wherein each selected path connects a first host and a second host.
Claim 14
Independent Claim
15 words
The method of any of the preceding claims wherein one of said parameters is bandwidth.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.