Granted Patent B2

US 12,355,578 · App. 17/695,485 · Granted Jul 8, 2025

Inventors: Daehyeok Kim (Redmond, WA); Jitendra Padhye (Redmond, WA); Shachar Raindel (Redmond, WA); Wei Bai (Redmond, WA)

Assignee: Microsoft Technology Licensing, LLC

H04L1/189H04L45/7453H04L2212/00

Abstract

Claims (145)

1. A method for packet level redundancy in a distributed computing system having a plurality of hosts interconnected by a computer network, the method comprising:

receiving, at a source host in the distributed computing system, an original packet to be transmitted to an application executing at a destination host in the distributed computing system via the computer network; and

in response to receiving the original packet, at the source host,

generating a duplicated packet based on the received original packet, the duplicated packet being a copy of the received original packet;

encapsulating the original and duplicated packets with first and second outer headers having first and second header values, respectively, the first and second header values being different from each other;

transmitting the original packet from the source host to the destination host via a first network path in the computer network according to the first header value, wherein transmitting the original packet from the source host to the destination host via the first network path in the computer network includes determining the first network path according to the first header value based on a routing table at a network component in the computer network; and

transmitting the duplicated packet from the source host to the destination host via a second network path in the computer network according to the second header value, the second network path being different from the first network path, wherein transmitting the duplicated packet from the source host to the destination host via the second network path in the computer network includes determining the second network path according to the second header value based on the same routing table at the same network component in the computer network.

2. The method of claim 1 , further comprising:

receiving, at the destination host, the transmitted original and duplicated packets via the first and second network paths, respectively; and

upon receiving the original and duplicated packets,

de-duplicating the received original and duplicated packets; and

transmitting the de-duplicated original and duplicated packets to the application executing at the destination host.

3. The method of claim 1 , further comprising:

receiving, at the destination host, the transmitted original or duplicated packet via the first and second network paths, respectively; and

upon receiving the original or duplicated packet,

decapsulating the original or duplicated packet to remove the outer header;

deriving a hash value of one or more header values of the decapsulated original or duplicated packet;

determining whether the derived hash value is in a hash table; and

in response to determining that the derived hash value is not in the hash table,

retaining the received original or duplicated packet; and

adding the derived hash value to the hash table.

4. The method of claim 1 , further comprising:

receiving, at the destination host, the transmitted original or duplicated packet via the first and second network paths, respectively; and

upon receiving the original or duplicated packet,

decapsulating the original or duplicated packet to remove the outer header;

deriving a hash value of one or more header values of the decapsulated original or duplicated packet;

determining whether the derived hash value is in a hash table; and

in response to determining that the derived hash value is not in the hash table,

retaining the received original or duplicated packet;

adding the derived hash value to the hash table; and

purging the derived hash value in the hash table after a threshold time.

5. The method of claim 1 , further comprising:

receiving, at the destination host, the transmitted original or duplicated packet via the first and second network paths, respectively; and

upon receiving the original or duplicated packet,

decapsulating the original or duplicated packet to remove the outer header;

deriving a hash value of one or more header values of the decapsulated original or duplicated packet;

determining whether the derived hash value is in a hash table; and

in response to determining that the derived hash value is not in the hash table,

providing the received original or duplicated packet to the application executing at the destination host; and

adding the derived hash value to the hash table.

6. The method of claim 1 , further comprising:

receiving, at the destination host, the transmitted original or duplicated packet via the first and second network paths, respectively; and

upon receiving the original or duplicated packet,

decapsulating the original or duplicated packet to remove the outer header;

deriving a hash value of one or more header values of the decapsulated original or duplicated packet;

determining whether the derived hash value is in a hash table; and

in response to determining that the derived hash value is already in the hash table, discarding the received original or duplicated packet.

7. The method of claim 1 , further comprising:

receiving, at the destination host, the transmitted original or duplicated packet via the first and second network paths, respectively; and

upon receiving the original or duplicated packet,

decapsulating the original or duplicated packet to remove the outer header;

deriving a hash value of one or more header values of the decapsulated original or duplicated packet;

determining whether the derived hash value is in a hash table; and

in response to determining that the derived hash value is already in the hash table,

discarding the received original or duplicated packet; and

removing the derived hash value from the hash table.

8. The method of claim 1 wherein generating the duplicated packet is performed at one of:

an application executing at the source host;

an operating system at the source host;

a software driver of a Network Interface Card (“NIC”) at the source host; or

a co-processor of the NIC.

9. A computing device connectable to other computing devices in a distributed computing system by a computer network, comprising:

a processor;

a network interface card (“NIC”); and

a memory containing instructions executable by the processor to cause the computing device to:

upon receiving, at a source host in the distributed computing system, an original packet to be transmitted to an application executing at a destination host in the distributed computing system via the computer network,

generate a duplicated packet based on the received original packet, the duplicated packet being a copy of the received original packet;

encapsulate the original and duplicated packets with first and second outer headers having first and second header values, respectively, the first and second header values being different from each other;

transmit the original packet from the source host to the destination host via a first network path in the computer network according to the first header value, wherein transmitting the original packet from the source host to the destination host via the first network path in the computer network includes determining the first network path according to the first header value based on a routing table at a network component in the computer network; and

transmit the duplicated packet from the source host to the destination host via a second network path in the computer network according to the second header value, the second network path being different from the first network path, wherein transmitting the duplicated packet from the source host to the destination host via the second network path in the computer network includes determining the second network path according to the second header value based on the same routing table at the same network component in the computer network.

10. The computing device of claim 9 wherein the memory includes additional instructions executable by the processor to cause the computing device to:

upon receiving, at the destination host, the transmitted original and duplicated packets via the first and second network paths, respectively, de-duplicate the received original and duplicated packets; and

transmit the de-duplicated original and duplicated packets to the application executing at the destination host.

11. The computing device of claim 9 wherein the memory includes additional instructions executable by the processor to cause the computing device to:

upon receiving, at the destination host, the transmitted original or duplicated packet via the first and second network paths, respectively,

decapsulate the original or duplicated packet to remove the outer header;

derive a hash value of one or more header values of the decapsulated original or duplicated packet;

determine whether the derived hash value is in a hash table; and

in response to determining that the derived hash value is not in the hash table,

retain the received original or duplicated packet; and

add the derived hash value to the hash table.

12. The computing device of claim 9 wherein the memory includes additional instructions executable by the processor to cause the computing device to:

upon receiving, at the destination host, the transmitted original or duplicated packet via the first and second network paths, respectively, decapsulate the original or duplicated packet to remove the outer header; derive a hash value of one or more header values of the decapsulated original or duplicated packet;

determine whether the derived hash value is in a hash table; and

in response to determining that the derived hash value is not in the hash table,

retain the received original or duplicated packet;

add the derived hash value to the hash table; and

purge the derived hash value in the hash table after a threshold time.

13. The computing device of claim 9 wherein the memory includes additional instructions executable by the processor to cause the computing device to:

upon receiving, at the destination host, the transmitted original or duplicated packet via the first and second network paths, respectively,

decapsulate the original or duplicated packet to remove the outer header;

derive a hash value of one or more header values of the decapsulated original or duplicated packet;

determine whether the derived hash value is in a hash table; and

in response to determining that the derived hash value is not in the hash table,

provide the received original or duplicated packet to the application executing at the destination host; and

add the derived hash value to the hash table.

14. The computing device of claim 9 wherein the memory includes additional instructions executable by the processor to cause the computing device to:

upon receiving, at the destination host, the transmitted original or duplicated packet via the first and second network paths, respectively,

decapsulate the original or duplicated packet to remove the outer header;

derive a hash value of one or more header values of the decapsulated original or duplicated packet;

determine whether the derived hash value is in a hash table; and

in response to determining that the derived hash value is already in the hash table, discard the received original or duplicated packet.

15. The computing device of claim 9 wherein the memory includes additional instructions executable by the processor to cause the computing device to:

upon receiving, at the destination host, the transmitted original or duplicated packet via the first and second network paths, respectively,

decapsulate the original or duplicated packet to remove the outer header;

derive a hash value of one or more header values of the decapsulated original or duplicated packet;

determine whether the derived hash value is in a hash table; and

in response to determining that the derived hash value is already in the hash table,

discard the received original or duplicated packet; and

remove the derived hash value from the hash table.

16. A method for packet level redundancy in a distributed computing system having a plurality of hosts interconnected by a computer network, the method comprising:

receiving, at a source host in the distributed computing system, an original packet to be transmitted to an application executing at a destination host in the distributed computing system via the computer network; and

in response to receiving the original packet, at the source host,

generating a duplicated packet based on the received original packet, the duplicated packet being a copy of the received original packet;

encapsulating the original and duplicated packets with first and second outer headers having first and second header values, respectively, the first and second header values being different from each other;

transmitting the original and the duplicated packets from the source host to the destination host via a first network path and a second network path in the computer network according to the first header value and the second header value, respectively, wherein transmitting the original packet from the source host to the destination host via the first network path in the computer network includes determining the first network path according to the first header value based on a routing table at a network component in the computer network, and wherein transmitting the duplicated packet from the source host to the destination host via the second network path in the computer network includes determining the second network path according to the second header value based on the same routing table at the same network component in the computer network; and

de-duplicating the transmitted original and duplicated packets at the destination host before providing the de-duplicated original and duplicated packets to the application executing at the destination host.

17. The method of claim 16 , further comprising:

receiving, at the destination host, the transmitted original or duplicated packet via the first and second network paths, respectively; and

upon receiving the original or duplicated packet,

decapsulating the original or duplicated packet to remove the outer header;

deriving a hash value of one or more header values of the decapsulated original or duplicated packet;

determining whether the derived hash value is in a hash table; and

in response to determining that the derived hash value is not in the hash table,

retaining the received original or duplicated packet; and

adding the derived hash value to the hash table.

18. The method of claim 16 , further comprising:

receiving, at the destination host, the transmitted original or duplicated packet via the first and second network paths, respectively; and

upon receiving the original or duplicated packet,

decapsulating the original or duplicated packet to remove the outer header;

deriving a hash value of one or more header values of the decapsulated original or duplicated packet;

determining whether the derived hash value is in a hash table; and

in response to determining that the derived hash value is not in the hash table,

retaining the received original or duplicated packet;

adding the derived hash value to the hash table; and

purging the derived hash value in the hash table after a threshold time.

19. The method of claim 16 , further comprising:

receiving, at the destination host, the transmitted original or duplicated packet via the first and second network paths, respectively; and

upon receiving the original or duplicated packet,

decapsulating the original or duplicated packet to remove the outer header;

deriving a hash value of one or more header values of the decapsulated original or duplicated packet;

determining whether the derived hash value is in a hash table; and

in response to determining that the derived hash value is not in the hash table,

providing the received original or duplicated packet to the application executing at the destination host; and

adding the derived hash value to the hash table.

Assignments (2)

Continuity (1)

References Cited (11)