US5633866A
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-08-19
•
Granted: 1997-05-27
•
Expires: 2016-08-19
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-27 09:57
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: 27
Claim 1
Independent Claim
155 words
A method for routing packets in a network having a connection-oriented subnetwork, a plurality of routers coupled to said connection-oriented subnetwork, and a plurality of established virtual circuits, said method comprising the steps of: receiving a packet to be routed toward a packet destination; identifying a best existing virtual circuit from said plurality of established virtual circuits; determining whether said best existing virtual circuit is feasible for forwarding said packet toward said packet destination; determining whether said best existing virtual circuit is efficient for forwarding said packet toward said packet destination; forwarding said packet toward said packet destination using said best existing virtual circuit if said best existing virtual circuit is feasible and efficient; and 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 best existing virtual circuit is not both feasible and efficient.
Claim 2
Independent Claim
155 words
A method for routing packets in a network having a connection-oriented subnetwork, a plurality of routers coupled to said connection-oriented subnetwork, and a plurality of established virtual circuits, said method comprising the steps of: receiving a packet to be routed toward a packet destination; identifying a best existing virtual circuit from said plurality of established virtual circuits; determining whether said best existing virtual circuit is feasible for forwarding said packet toward said packet destination; determining whether said best existing virtual circuit is efficient for forwarding said packet toward said packet destination; forwarding said packet toward said packet destination using said best existing virtual circuit if said best existing virtual circuit is feasible and efficient; and 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 best existing virtual circuit is not both feasible and efficient.
Claim 3
Dependent Claim
42 words
The method of claim 1 wherein said step of determining whether said best existing virtual circuit is feasible includes determining whether said best existing virtual circuit is capable of forwarding said packet toward said packet destination and avoiding looping of said packet.
Claim 4
Dependent Claim
74 words
The method of claim 1 wherein said step of determining whether said best existing virtual circuit is feasible includes: determining a first distance to said packet destination considering all possible virtual circuits across said connection-oriented subnetwork; and determining a second distance from an opposite end of an established virtual circuit to said packet destination; and determining that said best existing virtual circuit is feasible if said second distance is less than said first distance.
Claim 5
Dependent Claim
43 words
The method of claim 1 wherein said step of determining whether said best existing virtual circuit is efficient includes testing said best existing virtual circuit to determine whether using said best existing virtual circuit 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 said 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
24 words
The method of claim 1 further including the step of analyzing each established virtual circuit for determining whether said virtual circuit should be dosed.
Claim 10
Dependent Claim
64 words
The method of claim 1 further including the steps of: providing a timer for each established virtual circuit for determining the utilization of said virtual circuit; resetting said timer when a packet is detected on said virtual circuit; incrementing said timer when a packet absence is detected on said virtual circuit; and closing said virtual circuit when said timer reaches a predetermined timeout value.
Claim 11
Dependent Claim
157 words
In a network having a plurality of routers attached to a connection-oriented subnetwork and a plurality of virtual circuits established to forward packets across said connection-oriented subnetwork, a method for routing said packets from source routers toward packet destinations comprising the steps of: receiving a packet to be routed toward a packet destination; determining a best existing virtual circuit from said plurality of established virtual circuits; determining whether said best existing virtual circuit is feasible, said best existing virtual circuit being feasible if capable of forwarding said packet toward said packet destination and avoiding looping of said packet; forwarding said packet toward said packet destination using said best existing virtual circuit if said best existing virtual circuit is feasible; and 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 best existing virtual circuit is not feasible.
Claim 12
Dependent Claim
157 words
In a network having a plurality of routers attached to a connection-oriented subnetwork and a plurality of virtual circuits established to forward packets across said connection-oriented subnetwork, a method for routing said packets from source routers toward packet destinations comprising the steps of: receiving a packet to be routed toward a packet destination; determining a best existing virtual circuit from said plurality of established virtual circuits; determining whether said best existing virtual circuit is feasible, said best existing virtual circuit being feasible if capable of forwarding said packet toward said packet destination and avoiding looping of said packet; forwarding said packet toward said packet destination using said best existing virtual circuit if said best existing virtual circuit is feasible; and 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 best existing virtual circuit is not feasible.
Claim 13
Dependent Claim
73 words
The method of claim 10 wherein said step of determining whether said best existing virtual circuit 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 said best existing virtual circuit is feasible if said second distance is less than said first distance.
Claim 14
Dependent Claim
22 words
The method of claim 10 wherein said connection-oriented subnetwork is an asynchronous transfer mode (ATM) subnetwork including a plurality of ATM switches.
Claim 15
Dependent Claim
24 words
The method of claim 10 further including the step of analyzing each established virtual circuit for determining whether said virtual circuit should be closed.
Claim 16
Dependent Claim
64 words
The method of claim 10 further including the steps of: providing a timer for each established virtual circuit for determining the utilization of said virtual circuit; resetting said timer when a packet is detected on said virtual circuit; incrementing said timer when a packet absence is detected on said virtual circuit; and closing said virtual circuit when said timer reaches a predetermined timeout value.
Claim 17
Independent Claim
165 words
A method for routing packets in a network having a connection-oriented subnetwork, a plurality of routers coupled to said connection-oriented subnetwork, and a plurality of established virtual circuits, said method comprising the steps of: receiving a packet to be routed toward a packet destination; identifying feasible virtual circuits from said plurality of established virtual circuits; determining an efficiency for each identified feasible virtual circuit, said efficiency representing the progress accomplished by said identified feasible virtual circuit in forwarding said packet toward said packet destination; identifying a best existing virtual circuit from said identified feasible virtual circuits based on said efficiency of each identified feasible virtual circuit; forwarding said packet toward said packet destination using said best existing virtual circuit if said best existing virtual circuit is identified; and 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 best existing virtual circuit is not identified.
Claim 18
Independent Claim
165 words
A method for routing packets in a network having a connection-oriented subnetwork, a plurality of routers coupled to said connection-oriented subnetwork, and a plurality of established virtual circuits, said method comprising the steps of: receiving a packet to be routed toward a packet destination; identifying feasible virtual circuits from said plurality of established virtual circuits; determining an efficiency for each identified feasible virtual circuit, said efficiency representing the progress accomplished by said identified feasible virtual circuit in forwarding said packet toward said packet destination; identifying a best existing virtual circuit from said identified feasible virtual circuits based on said efficiency of each identified feasible virtual circuit; forwarding said packet toward said packet destination using said best existing virtual circuit if said best existing virtual circuit is identified; and 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 best existing virtual circuit is not identified.
Claim 19
Dependent Claim
68 words
The method of claim 15 wherein said step of identifying feasible virtual circuits 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 said best existing virtual circuit is feasible if said second distance is less than said first distance.
Claim 20
Dependent Claim
22 words
The method of claim 15 wherein said connection-oriented subnetwork is an asynchronous transfer mode (ATM) subnetwork including a plurality of ATM switches.
Claim 21
Independent Claim
193 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 identifying a best existing virtual circuit from said plurality of established virtual circuits; means within said router for determining whether said best existing virtual circuit is feasible for forwarding said packet toward said packet destination; means within said router for determining whether said best existing virtual circuit is efficient for forwarding said packet toward said packet destination; means within said router for forwarding said packet toward said packet destination using said best existing virtual circuit, said means for forwarding being utilized only when said best existing virtual circuit is both feasible and efficient; 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 best existing virtual circuit is not both feasible and efficient.
Claim 22
Independent Claim
193 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 identifying a best existing virtual circuit from said plurality of established virtual circuits; means within said router for determining whether said best existing virtual circuit is feasible for forwarding said packet toward said packet destination; means within said router for determining whether said best existing virtual circuit is efficient for forwarding said packet toward said packet destination; means within said router for forwarding said packet toward said packet destination using said best existing virtual circuit, said means for forwarding being utilized only when said best existing virtual circuit is both feasible and efficient; 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 best existing virtual circuit is not both feasible and efficient.
Claim 23
Dependent Claim
45 words
The apparatus of claim 18 wherein said means for determining whether said best existing virtual circuit is feasible includes an algorithm executed by said router for determining whether said best existing virtual circuit is capable of forwarding said packet toward said packet destination without looping.
Claim 24
Dependent Claim
50 words
The apparatus of claim 18 wherein said means for determining whether said best existing virtual circuit is efficient includes an algorithm executed by said router for testing said best existing virtual circuit to determine whether using said best existing virtual circuit makes a particular minimum progress toward said packet destination.
Claim 25
Dependent Claim
22 words
The apparatus of claim 18 wherein said connection-oriented subnetwork is an asynchronous transfer mode (ATM) subnetwork including a plurality of ATM switches.
Claim 26
Dependent Claim
49 words
The apparatus of claim 18 further including: a timer for 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 27
Dependent Claim
28 words
The apparatus of claim 22 wherein said timer is capable of generating a signal to close said established virtual circuit when said timer reaches a predetermined timeout value.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-26 | 2000-11-25 | 2001-05-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-26 | 2004-11-25 | 2005-05-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-26 | 2008-11-25 | 2009-05-27 | $7700.00 | Window Closed / Lapsed |