Patent Document

CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is a divisional of U.S. patent application Ser. No. 10/830,779, filed Apr. 23, 2004, (currently allowed) which is herein incorporated by reference in its entirety. 
     
    
     BACKGROUND 
       [0002]    The present invention relates generally to computer systems and computer networks, and relates more particularly to content delivery over computer networks. Specifically, the present invention relates to a method and apparatus for adaptive forwarding of data over a computer network. 
         [0003]      FIG. 1  is a schematic illustration of one embodiment of a system  100  for forwarding data over a network. A wide range of end-to-end computing applications (including overlay networks, end-system multicast, proxy servers, network address translation and protocol tunneling, among others) use intermediaries, or forwarding nodes  106   1 - 106   n  (e.g., computing devices or routers), to route a stream  112  of data from a sender  102  (e.g., a server) to one or more receivers  104 . Receivers  104  may in turn deliver the data to one or more computing applications  108 . 
         [0004]    A typical problem with a system such as the system  100  is that a failure or disruption at any forwarding node disrupts the end-to-end chain, resulting in incomplete data delivery to the receiver(s). This is especially troublesome for large networks, as the probability of node failure increases with the number of forwarding nodes implemented. Conventional solutions for addressing node failure in a forwarding network include source-based repair such as a Transmission Control Protocol/Internet Protocol (TCP/IP) session between the data source and the receiver, packet number-based retransmission requests, and various application- and content-specific resiliency schemes (e.g., resuming File Transport Protocol at a specific byte offset from the start of a file, or resuming a video transmission at a specific frame number). However, these conventional solutions are subject to a number of limitations, including scalability limitations and the inability to adapt for use over a network using heterogeneous transports or delivering generic (non-content-specific) data streams. Accordingly, they are not appropriate for delivering data over an adaptively changing network using multiple point-to-point protocols in a content-independent manner. 
         [0005]    Thus, there is a need for a method and apparatus for failure-resilient forwarding of data over a computer network. 
       SUMMARY OF THE INVENTION 
       [0006]    In one embodiment, the present invention is a method and an apparatus for failure-resilient forwarding of data over a computer network. In one embodiment, a marker is introduced into the data stream, e.g., at the sending node and, in turn, allows forwarding nodes and/or receivers to efficiently track data stream reception. The marker functions as a checkpoint for the data transport process, and is identified and indexed at each forwarding node and receiver. Each receiver saves the marker prior to delivering data to an application, thereby designating a point in the data stream at which all preceding data is confirmed to have been delivered to the application. Thus, if a forwarding node fails, the receiver may request stream data from an alternate forwarding node by specifying to the alternate forwarding node to provide data starting from the marker. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0007]    So that the manner in which the above recited embodiments of the invention are attained and can be understood in detail, a more particular description of the invention, briefly summarized above, may be had by reference to the embodiments thereof which are illustrated in the appended drawings. It is to be noted, however, that the appended drawings illustrate only typical embodiments of this invention and are therefore not to be considered limiting of its scope, for the invention may admit to other equally effective embodiments. 
           [0008]      FIG. 1  is a schematic illustration of one embodiment of an end-to-end computing network; 
           [0009]      FIG. 2  is a flow diagram illustrating one embodiment of a method for enabling failure-resilient forwarding of data from a sender to one or more receivers according to the present invention; 
           [0010]      FIG. 3  is a table illustrating one method of distributing content using the system illustrated in  FIG. 2 ; 
           [0011]      FIG. 4  is a flow diagram illustrating one embodiment of a method for recovering lost data in a data stream; and 
           [0012]      FIG. 5  is a high level block diagram of the present failure-resilient forwarding system that is implemented using a general purpose computing device. 
       
    
    
       [0013]    To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to the figures. 
       DETAILED DESCRIPTION 
       [0014]    The present invention is a method and an apparatus for failure-resilient forwarding of data over a computer network. In one embodiment, a trigger condition, such as forwarding node failure, performance degradation, query, resource use imbalance and the like, initiates a network adaptation to correctly resume transmission reception of a data stream. 
         [0015]      FIG. 2  is a flow diagram illustrating the flow of data through one embodiment of a method  200  for enabling failure-resilient forwarding of data from a sender to one or more receivers according to the present invention. The method  200  is initialized at step  202  and proceeds to step  204 , where a sending node or a forwarding node (e.g., sender  102  or any one of the forwarding nodes  106  of  FIG. 1 ) obtains (in the case of the sender) or receives (in the case of the forwarding node) at least a portion of a data stream. In one embodiment, the data stream may simply be a portion or an arbitrarily sized data segment of a much larger data stream. Namely, a sequence of “chunks” or “portions” of the larger data stream is being sent from the sending node to a receiving node. In step  206 , the sender or a forwarding node injects a marker into the portion of the data stream, and forwards the “marked” data stream, with or without further modification, to one or more next recipient nodes in the network (e.g., one or more subsequent forwarding nodes or receiving nodes) via a point-to-point reliable transport protocol (e.g., a protocol that is packet loss resilient, such as TCP/IP and the like). The marker designates a reference point in the generic data stream and in one embodiment is a recognizable bit field with a unique identifier. The marker may be recognized by reserved bit sequences, fixed inter-marker offsets, or an offset specified by a prior marker. Thus, markers may be periodically injected into the data stream, so that a plurality of marked data streams is transported through the network. 
         [0016]    After injecting the marker in step  206 , the method  200  branches off into at least one of two possible subsequent processes. In steps  208 - 210 , the method executes steps in accordance with the function of a forwarding node; in steps  209 - 214 , the method  200  executes steps in accordance with the function of a receiving node. 
         [0017]    In step  208 , the method  200  inquires if the recipient of the marked data stream is a forwarding node. If the method  200  determines that the recipient is forwarding node, the method  200  proceeds to step  210 , where the method  200  inspects the received data stream, stores the data in a local buffer of the forwarding node, and creates or updates a marker index at the forwarding node. In one embodiment, the marker index that the method  200  updates comprises two key components: (1) a record of the most recently received marker; and (2) a record of each marker previously received and stored by the forwarding node. Once the method  200  has updated the marker index, the method  200  forwards the marked data stream to the next recipient(s) (e.g., one or more other forwarding nodes or receivers) in the network. The marked data stream is processed by the next recipient node(s) starting at the point in the method  200  just following step  206 , as indicated by the loop from step  210 . Thus, all forwarding nodes receive the marked data stream, relay the marked data stream to the next forwarding nodes or receivers, and index the markers. 
         [0018]      FIG. 3  is a schematic illustration of one embodiment of a marker index  300  according to the present invention, such as the marker index updated by the method  200  in step  210  of  FIG. 2 . In one embodiment, the marker index  300  is a table. As illustrated, the marker index  300  stores, for each marker (e.g., markers M 1 -M 3 ), the marker&#39;s unique identifier and its position in the local buffer. As will be further described below with reference to  FIG. 4 , this stored information may be used to recover data lost, for example, due to a forwarding node failure. 
         [0019]    Referring back to  FIG. 2 , if the method  200  concludes at step  208  that the recipient of the marked data stream is not a forwarding node, the method  200  terminates. 
         [0020]    Also after injecting the marker in step  206 , the method  200  inquires in step  209  if the recipient is a receiving node. If the method  200  concludes that the recipient is a receiving node, the method  200  proceeds to step  212  and queues the stream data received by the receiver until the marker is encountered. In step  214 , the method  200  saves the marker and delivers the queued data (i.e., all undelivered, non-marked data preceding the marker in the data stream) to a process desiring the original data stream (e.g., an application or a storage process). Alternatively, if the method  200  concludes in step  208  that the recipient is not a receiving node, the method  200  terminates. 
         [0021]    In one embodiment, one or more nodes are both forwarding and receiving nodes. That is, a node may be adapted to both receive data for delivery to an application, and also to forward the received data on to another node. Thus, the node is capable of executing both the forwarding and the receiving methods contained within the method  200 . Thus, although the forwarding and receiving processes (e.g., steps  208 - 210  and  209 - 214 , respectively) are designated by sequential reference numerals, the reference numerals do not connote an order in which the processes occur. Therefore, those skilled in the art will appreciate that the forwarding and receiving methods are executed independently, and that the methods may actually occur simultaneously, or may occur one after the other in any order. Thus, the sequence of the reference numerals as they apply to steps  208 - 216  is not intended to be limiting in any sense. 
         [0022]    Thus, the markers injected into the data stream represent checkpoints for the data transport process. By saving the markers at the receivers, the method  200  designates points in the data stream where all preceding data has been delivered, reliably and in order, to the waiting application. The method  200  also serves the function of designating points in the data stream where any succeeding data has yet to be delivered. This saved marker information may be used to recover data lost, for example, due to a forwarding node failure. 
         [0023]      FIG. 4  is a flow diagram illustrating one embodiment of a method  400  for recovering lost data in a data stream. For example, the method  400  may be executed in the event that a forwarding node (e.g., a forwarding node  106  of  FIG. 1 ) fails (e.g., due to disconnection from the network or power failure) and thus ceases to forward data to subsequent recipients. The method  400  is initialized at step  402  and proceeds to step  404 , where the method  400  identifies a forwarding node failure and connects a receiver (or subsequent forwarding node) to an alternate forwarding node, or a “backup node” (e.g., a node that preceded the failed node in the routing path). Alternatively, the method  400  may connect the receiver to any “sister” node of the failed forwarding node that is still receiving the data stream. In one embodiment, the backup node is selected for efficiency. For example, if the failed node is node X n  in  FIG. 1 , then the backup node can be selected to be node X 1  or node X n+1 . The selection of the proper node can be based on distance, delay, computational cost and the like. 
         [0024]    The method  400  then proceeds to step  406 , where the method  400  requests, from the backup node, the stream data starting from the last marker, M, saved by the receiver. In an alternative embodiment, the method  400  may request the stream data starting from a specified position after the last marker M (e.g., three bits after the marker M). The request includes the unique identifier for the marker M. In step  407 , the method  400  inquires if the backup node will accept the request presented in step  406 . If the backup node rejects the request, the method  400  returns to step  404  and connects to another backup node. Alternatively, if the backup node accepts the request in step  407 , the method  400  enables the backup node to look up the marker M in the backup node&#39;s marker index. If the marker M is present, the backup node begins sending the marked data stream, using the location of the marker M in its local buffer as the starting point. In one embodiment, any data residing in the local buffer past the point of the marker M is discarded. 
         [0025]    In step  408 , the method  400  resets a queue “write pointer” for the receiver to a position immediately following the marker M. The method  400  also erases data following the write pointer in the local buffer, and the receiver will now start queuing data over the new connection from the new forwarding node. As the marked data stream arrives at the receiver over the new connection from the backup node, the arriving data stream overwrites any data following the marker M in the receiver&#39;s local buffer. In an alternative embodiment, the method  400  may request discrete portions of the marked data stream from multiple backup nodes. 
         [0026]    At step  410 , the method  400  inquires if the next marker, M+1, has arrived at the receiver. If the next marker M+1 has arrived, the method  400  delivers data queued by the receiver (minus the marker M) to an application requesting the data at step  412 . If the next marker M+1 has not arrived, the method  400  continues to queue data over the new connection from the backup node. Those skilled in the art will recognize that steps  408 - 412  of the method  400  are steps typically executed by a receiver node; they have been discussed here, in the context of the method  400 , to illustrate the method by which the receiver mode may implement such steps in conjunction with the recovery of lost data. 
         [0027]    The method  400  is therefore able to repair failures accurately and efficiently by resuming data transmission at the point of interruption. Moreover, as the repair only requires communication with a nearby forwarding/backup node, repair paths are short and network load is fairly distributed. The method  400  also works at the application layer with any reliable point-to-point transport protocol, can leverage existing point-to-point protocols, and may allow reframing and multi-protocol forwarding. Thus, the method  400  works independently of transport protocols, as well as independently of data stream content. 
         [0028]      FIG. 5  is a high level block diagram of the present failure-resilient forwarding system that is implemented using a general purpose computing device  500 . In one embodiment, a general purpose computing device  500  comprises a processor  502 , a memory  504 , a failure-resilient forwarding mechanism or module  505  and various input/output (I/O) devices  506  such as a display, a keyboard, a mouse, a modem, and the like. In one embodiment, at least one I/O device is a storage device (e.g., a disk drive, an optical disk drive, a floppy disk drive). It should be understood that the failure-resilient forwarding mechanism  505  can be implemented as a physical device or subsystem that is coupled to a processor through a communication channel. 
         [0029]    Alternatively, the failure-resilient forwarding mechanism  505  can be represented by one or more software applications (or even a combination of software and hardware, e.g., using Application Specific Integrated Circuits (ASIC)), where the software is loaded from a storage medium (e.g., I/O devices  506 ) and operated by the processor  502  in the memory  504  of the general purpose computing device  500 . Thus, in one embodiment, the failure-resilient forwarding mechanism  505  and the associated methods described herein with reference to the preceding Figures can be stored on a computer readable medium or carrier (e.g., RAM, magnetic or optical drive or diskette, and the like). 
         [0030]    Although the methods described herein have been discussed with reference to system recovery from node failures, those skilled in the art will appreciate that the present invention may have other applications in the field of content delivery. For example, the present invention may be implemented to assure reliable data delivery with any network reconfiguration, and for any reason. Other reconfiguration techniques may include finding a backup node using a centralized or distributed registry of nodes (e.g., a known server or a Domain Name Service (DNS) lookup), a distributed hash table lookup, or a broadcast search, among others. Other reasons for network reconfiguration may include responding to performance degradation, optimization of network resource utilization and load balancing, among others. 
         [0031]    Thus, the present invention represents a significant advancement in the field of content delivery. A method and apparatus are provided that enable efficient, failure-resilient forwarding of data over a network. The network is able to accurately and efficiently resume data transmission at the point of interruption, without transmitting redundant or out-of-order data to a receiver. To an application requesting data from a sender, the failure and recovery of the system are substantially transparent. Moreover, the methods of the present invention are not application specific, but may be adapted for use with any type of data stream, regardless of content, and with any type of reliable transport protocol. 
         [0032]    While foregoing is directed to the preferred embodiment of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow.

Technology Category: 5