US5699347A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for routing packets in networks having connection-oriented subnetworks
Assignee: RPX Clearinghouse LLC
•
Filing: 1996-07-18
•
Granted: 1997-12-16
•
Expires: 2016-07-18
Abstract
Abstract A system for routing packets in a network environment having a connection-oriented subnetwork, a plurality of routers coupled to said connection-oriented subnetwork, and a plurality of established virtual circuits. A packet is received by a router for forwarding toward a packet destination. A best existing virtual circuit across said connection-oriented subnetwork is identified from said plurality of established virtual circuits. The best existing virtual circuit is analyzed to determine whether it is both feasible and efficient for forwarding the packet toward the packet destination. If the best existing virtual circuit is both feasible and efficient, then the packet is forwarded using the best existing virtual circuit. If the best existing virtual circuit is either not feasible or inefficient, then a new virtual circuit is established to an optimal next hop router and the packet is forwarded using the new virtual circuit.
Inventors
- 👤 Ross W. Callon
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 01:39
CPC Classifications
H; H04; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L; H04L45/00; H04L45/02; H04L45/10; H04L45/22; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5619; H04L2012/5629; H04L2012/5631; H04L2012/5636; H04L45/24; H04L45/247
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
109 words
A method for routing packets in a network having a connection-oriented subnetwork and a plurality of virtual circuits established across said connection-oriented subnetwork, said method comprising the steps of: receiving a packet to be routed toward a packet destination; determining whether one of said virtual circuits is feasible for forwarding said packet toward said packet destination; forwarding said packet toward said packet destination using one of said virtual circuits if one of said virtual circuits is feasible; and establishing a new virtual circuit across said connection-oriented subnetwork and forwarding said packet toward said packet destination using said new virtual circuit if said plurality of virtual circuits are not feasible.
Claim 2
Independent Claim
109 words
A method for routing packets in a network having a connection-oriented subnetwork and a plurality of virtual circuits established across said connection-oriented subnetwork, said method comprising the steps of: receiving a packet to be routed toward a packet destination; determining whether one of said virtual circuits is feasible for forwarding said packet toward said packet destination; forwarding said packet toward said packet destination using one of said virtual circuits if one of said virtual circuits is feasible; and establishing a new virtual circuit across said connection-oriented subnetwork and forwarding said packet toward said packet destination using said new virtual circuit if said plurality of virtual circuits are not feasible.
Claim 3
Dependent Claim
42 words
The method of claim 1 wherein said step of determining whether one of said virtual circuits is feasible includes determining whether one of said virtual circuits is capable of forwarding said packet toward said packet destination and avoiding looping of said packet.
Claim 4
Dependent Claim
73 words
The method of claim 1 wherein said step of determining whether one of said virtual circuits is feasible includes: determining a first distance to said packet destination considering all possible virtual circuits across said connection-oriented subnetwork; determining a second distance from an opposite end of an established virtual circuit to said packet destination; and determining that one of said virtual circuits is feasible if said second distance is less than said first distance.
Claim 5
Dependent Claim
41 words
The method of claim 1 further including the step of determining whether one of said virtual circuits is efficient by testing said virtual circuits to determine whether one of said virtual circuits makes a particular minimum progress toward said packet destination.
Claim 6
Dependent Claim
26 words
The method of claim 4 wherein said minimum progress toward said packet destination is a predetermined fraction of the progress made by an optimal virtual circuit.
Claim 7
Dependent Claim
28 words
The method of claim 4 wherein said minimum progress toward said packet destination is a predetermined fraction of a cost associated with traversing a best existing virtual circuit.
Claim 8
Dependent Claim
22 words
The method of claim 1 wherein said connection-oriented subnetwork is an asynchronous transfer mode (ATM) subnetwork including a plurality of ATM switches.
Claim 9
Dependent Claim
23 words
The method of claim 1 further including the step of analyzing each virtual circuit for determining whether said virtual circuit should be closed.
Claim 10
Dependent Claim
66 words
The method of claim 1 further including the steps of: providing a timer associated with each virtual circuit for determining the utilization of said virtual circuit; resetting said timer when a packet is detected on said associated virtual circuit; incrementing said timer when a packet absence is detected on said associated virtual circuit; and closing said virtual circuit if said timer reaches a predetermined timeout value.
Claim 11
Independent Claim
148 words
An apparatus for forwarding packets in a network having a connection-oriented subnetwork, a plurality of routers coupled to said connection-oriented subnetwork, and a plurality of virtual circuits established across said connection-oriented subnetwork, said apparatus comprising: a router capable of receiving a packet to be forwarded toward a packet destination; means within said router for determining whether one of said plurality of virtual circuits is feasible for forwarding said packet toward said packet destination; means within said router for forwarding said packet toward said packet destination using one of said virtual circuits, said means for forwarding being utilized when one of said virtual circuits is feasible; and means within said router for establishing a new virtual circuit across said connection-oriented subnetwork to an optimal next hop router and forwarding said packet toward said packet destination using said new virtual circuit if said plurality, of virtual circuits are not feasible.
Claim 12
Independent Claim
148 words
An apparatus for forwarding packets in a network having a connection-oriented subnetwork, a plurality of routers coupled to said connection-oriented subnetwork, and a plurality of virtual circuits established across said connection-oriented subnetwork, said apparatus comprising: a router capable of receiving a packet to be forwarded toward a packet destination; means within said router for determining whether one of said plurality of virtual circuits is feasible for forwarding said packet toward said packet destination; means within said router for forwarding said packet toward said packet destination using one of said virtual circuits, said means for forwarding being utilized when one of said virtual circuits is feasible; and means within said router for establishing a new virtual circuit across said connection-oriented subnetwork to an optimal next hop router and forwarding said packet toward said packet destination using said new virtual circuit if said plurality, of virtual circuits are not feasible.
Claim 13
Dependent Claim
47 words
The apparatus of claim 10 wherein said means for determining whether one of said plurality of virtual circuits is feasible includes an algorithm executed by said router for determining whether one of said virtual circuits is capable of forwarding said packet toward said packet destination without looping.
Claim 14
Dependent Claim
53 words
The apparatus of claim 10 further including means for determining whether one of said plurality of virtual circuits is efficient, wherein said means includes an algorithm executed by said router for testing said virtual circuits to determine whether using one of said virtual circuits makes a particular minimum progress toward said packet destination.
Claim 15
Dependent Claim
22 words
The apparatus of claim 10 wherein said connection-oriented subnetwork is an asynchronous transfer mode (ATM) subnetwork including a plurality of ATM switches.
Claim 16
Dependent Claim
50 words
The apparatus of claim 10 further including: a timer associated with each established virtual circuit for determining the utilization of said virtual circuit, said timer capable of being reset when a packet is detected on said virtual circuit and incremented when a packet absence is detected on said virtual circuit.
Claim 17
Dependent Claim
28 words
The apparatus of claim 14 wherein said timer is capable of generating a signal to close said established virtual circuit when said timer reaches a predetermined timeout value.
Claim 18
Independent Claim
165 words
A method for performing layered routing of packets in a network having a plurality of virtual circuits, said method comprising the steps of: receiving a packet to be routed toward a packet destination; calculating a first path to said packet destination using an enhanced topology and considering said plurality of virtual circuits; forwarding said packet using said first path if said first path is feasible; calculating a second path to said packet destination if said first path is not feasible, said second path using an enhanced topology and considering all available routes; forwarding said packet using said second path if said second path is feasible and said first path is not feasible; calculating a third path to said packet destination if said first and second paths are not feasible, said third path using a logical router topology and considering all available routes; and forwarding said packet using said third path if said third path is feasible and said first and second paths are not feasible.
Claim 19
Independent Claim
165 words
A method for performing layered routing of packets in a network having a plurality of virtual circuits, said method comprising the steps of: receiving a packet to be routed toward a packet destination; calculating a first path to said packet destination using an enhanced topology and considering said plurality of virtual circuits; forwarding said packet using said first path if said first path is feasible; calculating a second path to said packet destination if said first path is not feasible, said second path using an enhanced topology and considering all available routes; forwarding said packet using said second path if said second path is feasible and said first path is not feasible; calculating a third path to said packet destination if said first and second paths are not feasible, said third path using a logical router topology and considering all available routes; and forwarding said packet using said third path if said third path is feasible and said first and second paths are not feasible.
References Cited (Backward Citations)
US5115495A
Cited
US5128926A
Cited
US5251205A
Cited
US5233604A
Cited
US5491690A
Cited
US5497368A
Cited
US5452294A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-12-15 | 2001-06-16 | 2001-12-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-12-15 | 2005-06-16 | 2005-12-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-12-15 | 2009-06-16 | 2009-12-16 | $7700.00 | Window Closed / Lapsed |