Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
2000-04-06
2003-12-30
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C370S400000
Reexamination Certificate
active
06671819
ABSTRACT:
BACKGROUND OF THE INVENTION
A. Field of the Invention
The present invention relates generally to routing systems and, more particularly, to systems and methods for routing packets through a network on alternate paths.
B. Description of Related Art
Currently, several types of communication systems exist, including wireless, wired, optical, and hybrid wireless/wired/optical communication systems. Often times, these systems include a network of interconnected nodes. Each node connects to neighboring nodes via a link. The link may be a wireless, wired, or optical communication channel, depending on the type of system in which it is used.
Communication through these systems involves transmitting a packet of data from a source node to a destination node. Often times, a path from the source node to the destination node is predetermined so that each node can determine how to route a received packet. Sometimes, however, the path is established on-the-fly based on cost factors, such as shortest path, signal strength, connection speed, etc. In these cases, the nodes route a packet to minimize the cost of sending the packet from the source node to the destination node.
If a packet transmitted by a node is not successfully received by the next node in one of these systems, the transmission will fail. The source node usually learns of the transmission failure after a timer expires (i.e., after a timeout). In this case, the source node must try to resend the packet, possibly on a different path.
As a result, a need exists to improve the transmission of packets through a network by using alternate paths to minimize the effects of transmission failures between nodes.
SUMMARY OF THE INVENTION
Systems and methods consistent with the present invention address this need by determining, at each node, the next best path on which to transmit a packet when transmission on a first path fails.
In accordance with the purpose of the invention as embodied and broadly described herein, a network for routing packets includes multiple nodes. A first node has a direct link to a second node. The first node receives a packet and identifies a primary next hop to which to transmit the packet. The primary next hop identifies at least the second node. The first node transmits the packet to the second node, determines whether the transmission was successful, and identifies at least a third node when the transmission to the second node was unsuccessful.
The first node identifies the third node by: finding a node in the network that has a direct link to both the first and second nodes; identifying at least one alternate next hop, assuming that the link between the first and second nodes is unavailable, determining the cost associated with each of the alternate next hops, and selecting one of the alternate next hops based on the determined cost; or retrieving a predetermined alternate next hop from a forwarding table stored by the first node. The first node then transmits the packet to the third node for forwarding to the second node.
In another implementation consistent with the present invention, a method prevents lost or looping packets in a network. The method includes receiving a packet at a first node; transmitting the packet to a second node on a primary path; determining whether the transmission was successful; identifying a third node on an alternate path when the transmission to the second node was unsuccessful; adding a header to the packet, the header identifying at least an address of the second node; transmitting the packet to the third node; analyzing the packet by the third node to identify the address of the second node from the header; sending the packet to the second node using the identified address; receiving the packet at the second node; and clearing the header by the second node.
REFERENCES:
patent: 4679189 (1987-07-01), Olson et al.
patent: 5115495 (1992-05-01), Tsuchiya et al.
patent: 5142531 (1992-08-01), Kirby
patent: 5173689 (1992-12-01), Kusano
patent: 5218601 (1993-06-01), Chujo et al.
patent: 5235599 (1993-08-01), Nishimura et al.
patent: 5452294 (1995-09-01), Natarajan
patent: 5455865 (1995-10-01), Perlman
patent: 5513345 (1996-04-01), Sato et al.
patent: 5548639 (1996-08-01), Ogura et al.
patent: 5590118 (1996-12-01), Nederlof
patent: 5615254 (1997-03-01), Qiu et al.
patent: 5646936 (1997-07-01), Shah et al.
patent: 5649108 (1997-07-01), Spiegel et al.
patent: 5732072 (1998-03-01), Thanner et al.
patent: 5754543 (1998-05-01), Seid
patent: 5805818 (1998-09-01), Perlman et al.
patent: 5940372 (1999-08-01), Bertin et al.
patent: 5953312 (1999-09-01), Crawley et al.
patent: 6111673 (2000-08-01), Chang et al.
patent: 6141319 (2000-10-01), Dighe et al.
patent: 6157621 (2000-12-01), Brown et al.
patent: 6215765 (2001-04-01), McAllister et al.
patent: 6282170 (2001-08-01), Bentall et al.
patent: 6347078 (2002-02-01), Narvaez-Guarnieri et al.
patent: 6430150 (2002-08-01), Azuma et al.
patent: 6473405 (2002-10-01), Ricciulli
patent: 6519062 (2003-02-01), Yoo
patent: 6530032 (2003-03-01), Shew et al.
patent: 6556577 (2003-04-01), Hjalmtysson et al.
patent: 6580715 (2003-06-01), Bare
Manning Keith W.
Passman William S.
Weinstein Joseph J.
Wood Susan L.
Zavgren John R.
Baker Stephen M.
BBNT Solutions LLC
Suchyta Leonard Charles
Weixel James K.
LandOfFree
System and methods routing packets on alterate paths does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and methods routing packets on alterate paths, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and methods routing packets on alterate paths will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3148540