Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
2000-07-31
2004-06-15
Le, Dieu-Minh (Department: 2114)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C370S218000
Reexamination Certificate
active
06751746
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer networks, and, more particularly, to a method and apparatus for maintaining a datastream between network elements (e.g., routers) in a network.
2. Description of the Related Art
A wide variety of communications alternatives are currently available to telecommunications users. For example, e-mail and other forms of data communication can be used to relay messages and other information over existing data networks. Also, facsimile transmission of printed matter is available through what is commonly referred to as a stand-alone fax machine. Alternatively, fax-modem communication systems are currently available for personal computer users which combine the operation of a facsimile machine with the word processor of a computer to transmit documents held on computer disk. Modem communication over telephone lines in combination with a personal computer is also available to permit the transfer of files between computers. Simultaneous voice and modem data can also be transmitted over the lines using any one of several methods. Personal communications systems that combine a wide variety of communication functions into an integrated hardware-software product allow the user to conveniently choose from a number of communication modes. For example, personal communications systems exist which allow multiple users to efficiently communicate with one another using high quality voice over data communications links.
In fact, such teleconferencing capabilities have been extended to wide-area networks (WANs) such as the Internet. Voice-over-Internet-Protocol (VoIP), for example, is becoming a popular method of communication, supplanting traditional telephone services. Many other such methods of transferring media have come into use as the Internet has matured, including streaming audio, instant messaging and the like. However, for many such techniques, a failure within the network which such information passes can present unacceptable performance penalties. This is especially true for real-time or near-real-time applications (e.g., human conversations), in which dropouts and other outages can be most aggravating to users.
For example, consider a VoIP connection that uses real-time protocol (RTP) over a UDP/IP network infrastructure (e.g., the Internet), and the effects of a failure in one of the intermediate network links or network elements (e.g., a router or switch) between the connection's end-points. Clearly, VoIP packets will be dropped until such time as an alternate route through the network has been identified, and packets are re-routed along this new route.
Traditionally, users have relied on a routing protocol (e.g., open shortest path first or OSPF), to detect link/device failures and to re-compute a new path between the given pair of source and destination devices. Unfortunately, the time required for a breakdown to be discovered, and for the routing protocol (e.g., OSPF) to advertise the link-state and recompute the shortest path, is unacceptably high for most real-time applications, including VoIP. For example, in some VoIP systems, an interruption in transfer of packets for a duration 150 ms or more is considered unacceptably large. The delay in restoration is even larger if packets are label-switched. This is so because, in such a case, a new label-switched path must be set up before transfer of packets can resume.
What is therefore needed is a method and apparatus capable of handling failures in network infrastructure that affect a datastream traversing the network, while maintaining acceptable throughput in such situations. Such an approach is preferably capable of maintaining throughput, despite such failures, such that the interruptions are not noticeable to a user of the system.
SUMMARY OF THE INVENTION
The present invention, in various embodiments, addresses the aforementioned problems by providing a method and apparatus that address the problem of recovery from a breakdown of a path used to support datastreams traversing a network. Preferably, the technique employs a pair of node- or link-disjoint paths, which are identified and configured a-priori. If packet transfer is forced to occur along these paths (e.g., by the use of label-switching techniques), then failure within one of the two paths does not interrupt transfer of packets from the source to the destination. The present invention achieves uninterrupted transfer of packets by causing the source to replicate packets and send a copy along each path. Each intermediate node along each path then send the packet stream along the identified path. Finally, the destination node detects and discards duplicate packets based on sequence numbers contained within each packet. If a failure occurs in the path currently being used, no action need be taken, because the destination will continue to receive those packets being sent along the other path.
The techniques described herein provide several advantages. Chief among them is the ability to efficiently and effectively maintain a datastream (i.e., network connection) even though a failure may occur in the network path being used. Moreover, these techniques address the fundamental concern of maintaining such connections in a way that is transparent to the users of such a system. Simplicity and ease of implementation are also attractive features of these techniques. For example, no switching between the paths need be effected, because the destination simply uses whatever packets it receives and will continue to receive packets via the other path. Also discussed herein are computationally efficient techniques for computing a pair of shortest node-disjoint paths (and, similarly, link-disjoint paths).
In one embodiment of the present invention, a method of operating a fault tolerant connection in a network is described. The network includes a number of network elements and a number of links. Each of the network elements is coupled to at least one other of the network elements by at least one of the links. The method identifies a first path and a second path. The first path is between a first one of the network elements and a second one of the network elements, as is the second path. Moreover, the first path and the second path are disjoint. This disjointedness can be any difference between the two paths (e.g., any combination of different network elements or links). For example, the disjointness can be either (a) link-disjoint or (b) node disjoint. Two paths are link-disjoint if they do not have any link in common. Similarly, two paths are node disjoint if they do not have any node in common. A packet is sent from the first one of the network elements via the first path, while a duplicate packet is sent from the first one of the network elements via the second path. The duplicate packet is a duplicate of the packet. Once these packets have been sent, at least one of the packet and the duplicate packet are received at the second one of the network elements.
REFERENCES:
patent: 4451827 (1984-05-01), Kahn et al.
patent: 5485465 (1996-01-01), Liu et al.
patent: 5530808 (1996-06-01), Hammond et al.
patent: 5617421 (1997-04-01), Chin et al.
patent: 5940771 (1999-08-01), Gollnick et al.
patent: 6081511 (2000-06-01), Carr et al.
patent: 6243381 (2001-06-01), Cai et al.
patent: 6271946 (2001-08-01), Chang et al.
patent: 6496477 (2002-12-01), Perkins et al.
patent: 6542469 (2003-04-01), Kelley et al.
patent: WO 00/13376 (2000-03-01), None
Orda et al. Routing with packet duplication and elimination in computer networks, IEEE transactions on communications, US, IEEE inc. New York, vol. 36, No. 7, Jul. 1, 1988, pp. 860-866.*
R. Callon, A. Vishwanathan, E. Rosen, “Multiprotocol Label Switching Architecture”, Work in Progress, draft-ietf-mpls-arch-07.txt, Jul. 2000.
R. Callon, P. Doolan, N. Feldman, A. Fredette, G. Swallow, A. Viswanathan, “A Framework for Multiprotocol Label Switching”, draft-ietf-mpls-framework-05.txt, Sep. 1999.
“Data Structures And Algorithms”, by Alfred V. Aho, John E. Hopcroft,
Jain Bijendra N.
McCloghrie Keith
Campbell Stephenson Ascolese LLP
Cisco Technology Inc.
Le Dieu-Minh
LandOfFree
Method and apparatus for uninterrupted packet transfer using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for uninterrupted packet transfer using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for uninterrupted packet transfer using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3365698