Availigent, Inc.

Eternal Systems, Inc.

Nevion Usa, Inc.

United States of America As Represented by the Secretary of the Air Force

Peter Michael Melliar-Smith

Louise Elizabeth Moser

Chin Chye Koh

Ruppert Koch

Sanjay Hortikar

Wenbing Zhao

This invention concerns packet recovery for real-time (live) multi-media communication over packet-switched networks like the Internet. Such communication includes video, audio, data or any combination thereof. The invention comprises forward error correction (FEC) algorithms addressing both random and burst packet loss and errors, and that can be adjusted to tradeoff the recoverability of missing packets and the latency incurred.

Forward error correction method

This invention relates generally to a packet recovery algorithm for real-time (live) multi-media communication over packet-switched networks, such as the Internet. Such multi-media communication includes video, audio, data or any combination thereof. More specifically, the invention comprises a forward error correction (FEC) algorithm that addresses both random and burst packet loss and errors, and that can be adjusted to tradeoff the recoverability of missing packets and the latency incurred. The transmitter calculates parity packets for the rows, columns and diagonals of a block of multi-media data packets using the exclusive or (XOR) operation and communicates the parity packets along with the multi-media data packets to the receiver. The receiver uses the parity packets to recover missing multi-media data packets in the block. The FEC algorithm is designed to be able to recover long bursts of consecutive missing data packets. If some parity packets are missing, they too can be recovered using an extra single parity packet, so that they can be used to recover other missing data packets. The invention applies to both one-way real-time streaming applications and two-way real-time interactive applications, and to both wired and wireless networks. The invention retains backwards compatibility with existing standards governing FEC for professional video over IP networks.

Forward error correction for burst and random packet loss for real-time multi-media communication

A consistent time service that provides a method of maintaining deterministic clock-related operations for a group of replicas in a fault-tolerant distributed system. A consistent clock synchronization algorithm is utilized that yields a single consistent group clock for the replicas in the group, and does not require synchronization of the underlying physical hardware clocks. The consistent group clock ensures the determinism of the replicas in the group with respect to clock-related operations, is monotonically increasing, has bounded increment, skew and drift. The consistent time service provides benefits for active replication during normal operation, as well as passive replication and semi-active replication to ensure a consistent monotonically increasing clock when the primary replica fails and a backup replica takes over as the new primary replica. The consistent time service provided is transparent to the application and guarantees group clock consistency despite replica failures or adding new or repaired replicas.

Consistent time service for fault-tolerant distributed systems

A method for checkpointing a multithreaded application program, based on the egalitarian and competitive active replication strategy. The invention enables different threads to be checkpointed at different times in such a way that the checkpoints restore a consistent state of the threads at a new or recovering replica, even though the threads operate concurrently and asynchronously. Separate checkpoints are generated for the local state of each thread and for the data that are shared between threads and are protected by mutexes. The checkpoint of the shared data is communicated in a special message that also determines the order in which the claims of mutexes are granted to the threads. A source-code preprocessor tool is described for inserting code into an application program to checkpoint the state of the thread during normal operation and to restore the state of the thread from the checkpoint subsequently.

Consistent asynchronous checkpointing of multithreaded application programs based on active replication

Methods of transparent connection failover allowing a remote computer (i.e., a client), to continue to use a network connection to communicate with one of at least two or more other computers (i.e., the backup servers) over a network, when one of the other computers (i.e., the primary server) fails. With the mechanisms of this invention, there is no need for the client to establish a new connection to a backup server when the primary server fails. The failover is preferably executed within a bridge layer between the TCP layer and the IP layer of the server's TCP/IP stack. No modifications are required to the network infrastructure, the client's TCP/IP stack, the client application or the server application. The methods support active or semi-active replication of the server application, and do not require rollback of the application during failover. The invention also provides mechanisms for bringing up new backup servers.

Transparent TCP connection failover

A method and system for transparent consistent active replication of multithreaded application programs is described. At each replica, control messages that contain mutex ordering information indicating the order in which threads in the replicas claim mutexes are multicast, and the control messages are delivered using a multicast group communication protocol that delivers the messages in an order that determines the order in which the operating system's thread library grants the claims of mutexes to the threads in the replicas. Because the replicas receive the same messages in the same source order, the corresponding threads in the different replicas are granted their corresponding claims to the corresponding mutexes in the same order, maintaining strong replica consistency.

Transparent consistent active replication of multithreaded application programs

A system and method for replicating a multithreaded application program using a semi-active or passive replication strategy, wherein the application program executes under the control of an operating system having a thread library. The method comprises piggybacking mutex ordering information at the Primary replica onto regular multicast messages specifying the order in which threads in the Primary replica have been granted their claims to mutexes; and receiving the multicast messages at a Backup replica containing the mutex ordering information which determines the order in which threads in the Backup replica are granted mutexes. Thread library interpositioning is preferably utilized to intercept calls to functions in the operating system's thread library, so that the system and method of the invention may be implemented transparently. The invention enforces strong replica consistency without the need to count instructions, add significant messaging overhead, or modify application code.

Transparent consistent semi-active and passive replication of multithreaded application programs

A method and mechanisms for checkpointing objects, processes and other components of a multithreaded application program, based on the leader-follower strategy of semi-active or passive replication, where it is not possible to stop and checkpoint all of the threads of the object, process or other component simultaneously. Separate checkpoints are generated for the local state of each thread and for the data that are shared between threads and are protected by mutexes. The invention enables different threads to be checkpointed at different times in such a way that the checkpoints restore a consistent state of the threads between the existing replicas and a new or recovering replica, even though the threads operate concurrently and asynchronously. The checkpoint of the shared data is piggybacked onto regular messages along with ordering information that determines the order in which the mutexes are granted to the threads.

Consistent asynchronous checkpointing of multithreaded application programs based on semi-active or passive replication

This invention defines a method and mechanisms for maintaining a consistent group membership, based on the leader-follower strategy of Semi-Active or Passive replication. Each member of the group is assigned a rank, and a precedence, determined by the order in which it is added to the group. The Primary maintains the membership of the group, while each Backup monitors the behavior of the Primary. When a Backup detects that the Primary is faulty, the Backup announces that it is the new Primary and removes the faulty Primary from the membership of the group. The group membership algorithm disclosed here does not require a consensus decision to reconfigure the membership and effects a membership change more quickly in the common case where the Backup of lowest rank takes control as the new Primary when it determines that the existing Primary failed.

Consistent group membership for semi-active and passive replication

Mechanisms for achieving consistent message ordering within a fault-tolerant distributed computer system based on semi-active or passive replication are described. The mechanisms communicate message ordering information from the primary replica to its backup replicas in such a way as to minimize the end-to-end request/response time, to minimize the number of additional messages that are multicast, and to ensure that, in the event of a fault, a backup replica has, or can obtain, the messages and the message ordering information that it needs to reproduce the actions of the primary replica.

Consistent message ordering for semi-active and passive replication

Mechanisms for a Networked Enterprise Server that provide fault tolerance for computer programs that interact with computer programs within and between enterprises over a communication network, such as the Internet or a virtual private network. Fault tolerance is provided by unifying transaction processing and object or process replication. Transaction processing is used in this invention to protect the local data and processing against faults, while replication is used to protect the processing and communication that span multiple enterprises.

Fault tolerance for computer programs that operate over a communication network

A process that assists a computer programmer to perform an upgrade to a computer program while that program continues to operate and provide service. The upgrade process includes three phases: (1) the preparation by a computer programmer of a new computer program P&Prime; that is to replace an existing computer program P, (2) an offline preparation of the upgrade from P to P&Prime; with the assistance of the computer programmer, and (3) an online, fully automatic, live upgrade from P to P&Prime;.

Live upgrade process for object-oriented programs

A broadcast protocol system which uses a plurality of distributed computers which are electrically connected by a broadcast medium. Each message is broadcast to all computers with a header in which there is a message identifier containing the identity of the broadcasting processor and a message sequence number. A retransmission number is also included in the identifier to distinguish retransmissions. Each processor maintains an acknowledgement list of message identifiers with positive and negative acknowledgements.

Growing community of inventors

Santa Barbara, CA, United States of America

Peter Michael Melliar-Smith