Back to results
US 12,217,308 B2Granted
In-order processing of network packets
AssigneeNasdaq, Inc.
InventorsSandeep Rao, Thomas Fay, Dominick Paniscotti, Yuriy Buglo
Life of this patent
Estimating the term…
Abstract
The described technology relates to a real-time processing of network packets. An example system relates to reordering messages received at a server over a communication network from distributed clients, in order to, among other things, eliminate or at least substantially reduce the effects of jitter (delay variance) experienced in the network. The reordering of messages may enable the example data processing application to improve the consistency of processing packets in the time order of when the respective packets entered a geographically distributed network.
Claims19
A distributed computer system for addressing variance in network communication latency from multiple different physical locations, the distributed computer system comprising:
- a communication infrastructure;
- a server infrastructure system comprising a memory and a reorder buffer configured in the memory and associated with a flush timer;
- and
- a plurality of gateway infrastructure systems located at a plurality of geographically distributed locations at different distances from the server infrastructure system and connected to the server infrastructure system by the communication infrastructure, wherein packet latencies from respective gateway infrastructure systems to the server infrastructure system over respectively different paths through the communications infrastructure are different,
- wherein each of the plurality of gateway infrastructure systems is configured to perform operations comprising:
- receiving incoming data transaction request packets from one or more client computer systems;
- for each of the received incoming data transaction request packets:
- attaching a respective gateway timestamp to the incoming data transaction request packet, the respective gateway timestamp corresponding to either a time at which the incoming data transaction request packet is in the gateway infrastructure system or a time at which the incoming data transaction was in a network device located between the gateway infrastructure system and a client computer system from the one or more client computer systems from which the incoming data transaction request packet originated;
- and
- transmitting the gateway timestamp-attached data transaction request packet to the server infrastructure system via the communication infrastructure;
- and
- wherein the server infrastructure system is configured to perform operations comprising:
- receiving each of the gateway timestamp-attached data transaction request packets from the plurality of gateway infrastructure systems via the communication infrastructure;
- for each of the gateway timestamp-attached data transaction request packets:
- attaching a server timestamp to the gateway timestamp-attached data transaction request packet, the server timestamp corresponding to a time at which the gateway timestamp-attached data transaction request packet is in the server infrastructure system;
- determining a transaction delay based upon the gateway timestamp and the server timestamp attached to the server timestamp-attached data transaction request packet;
- comparing the transaction delay to a preset threshold time interval, and:
- if the transaction delay is less than the preset threshold time interval, assigning, using the flush timer, a respective flush time to the gateway timestamp-attached data transaction request packet and insert the gateway timestamp-attached transaction request packet into the reorder buffer;
- or
- if the transaction delay is not less than the preset threshold time interval, outputting the gateway timestamp-attached data transaction request packet to a data processing application without storing the gateway timestamp-attached data transaction request packet in the reorder buffer;
- reordering, using the reorder buffer, the server timestamp-attached data transaction request packets in order of oldest to newest of the respective gateway timestamps of the server timestamp-attached data transaction request packets, wherein the reordering is based on both the gateway timestamp and the server timestamp of respective ones of the server timestamp-attached data transaction request packets;
- and
- outputting the reordered server timestamp-attached data transaction request packets from the reorder buffer in an order of oldest to newest of the respective gateway timestamps and in accordance with the respective associated flush times, via a shared memory pipe, to the data processing application, wherein the data processing application is configured to process the data transaction request packets in order of receipt at the data processing application;
- wherein the server infrastructure system is configured to perform the reordering and the outputting such that the output server timestamp-attached data transaction request packets are received by the data processing application in order of arrival at the plurality of gateway infrastructure systems, even if the corresponding gateway timestamp-attached transaction request packets arrived out of order at the server infrastructure due to the different packet latencies and jitter in the communication infrastructure between the plurality of gateway infrastructure systems and the server infrastructure system.
21 more elements
A method for addressing variance in network communication latency from multiple different physical locations in a distributed computer system, the method performed using at least one processor of a server infrastructure system of the distributed computer system, wherein the server infrastructure system includes a reorder buffer and an associated flush timer and is connected through a communication infrastructure to a plurality of gateway infrastructure systems located at a plurality of geographically distributed locations at different distances from the server infrastructure system, wherein packet latencies from respective gateway infrastructure systems to the server infrastructure system over respectively different paths through the communications infrastructure are different, the method comprising:
- receiving each of a plurality of gateway timestamp-attached data transaction request packets from a plurality of gateway infrastructure systems via the communication infrastructure, wherein a respective gateway timestamp is attached to each gateway timestamp-attached data transaction request packet, the respective gateway timestamp corresponds to either a time at which a respective corresponding incoming data transaction request packet is in the gateway infrastructure system or in a network device located between the gateway infrastructure system and a client computer system from the one or more client computer systems from which the respective corresponding incoming data transaction request packet originated;
- for each of the gateway timestamp-attached data transaction request packets:
- attaching a server timestamp to the gateway timestamp-attached data transaction request packet, the server timestamp corresponding to a time at which the gateway timestamp-attached data transaction request packet is in the server infrastructure system;
- determining a transaction delay based upon the gateway timestamp and the server timestamp attached to the server timestamp-attached data transaction request packet;
- comparing the transaction delay to a preset threshold time interval, and:
- if the transaction delay is less than the preset threshold time interval, assigning, using the flush timer, a respective flush time to the gateway timestamp-attached data transaction request packet and insert the gateway timestamp-attached transaction request packet into the reorder buffer;
- or
- if the transaction delay is not less than the preset threshold time interval, outputting the gateway timestamp-attached data transaction request packet to a data processing application without storing the gateway timestamp-attached data transaction request packet in the reorder buffer;
- reordering, using the reorder buffer, the server timestamp-attached data transaction request packets in order of oldest to newest of the respective gateway timestamps of the server timestamp-attached data transaction request packets, wherein the reordering is based on both the gateway timestamp and the server timestamp of respective ones of the server timestamp-attached data transaction request packets;
- and
- outputting the reordered server timestamp-attached data transaction request packets from the reorder buffer in an order of oldest to newest of the respective gateway timestamps and in accordance with the respective associated flush times, via a shared memory pipe, to the data processing application, wherein the data processing application is configured to process the data transaction request packets in order of receipt at the data processing application;
- wherein the server infrastructure system is configured to perform the reordering and the outputting such that the output server timestamp-attached data transaction request packets are received by the data processing application in order of arrival at the plurality of gateway infrastructure systems, even if the corresponding gateway timestamp-attached transaction request packets arrived out of order at the server infrastructure due to the different packet latencies and jitter in the communication infrastructure between the plurality of gateway infrastructure systems and the server infrastructure system.
9 more elements
A non-transitory computer readable storage medium having stored therein computer program instructions for addressing variance in network communication latency from multiple different physical locations in a distributed computer system, the computer program instructions, when performed using at least one processor of a server infrastructure system of the distributed computer system, wherein the server infrastructure system includes a reorder buffer and an associated flush timer and is connected through a communication infrastructure to a plurality of gateway infrastructure systems located at a plurality of geographically distributed locations at different distances from the server infrastructure system and wherein packet latencies from respective gateway infrastructure systems to the server infrastructure system over respectively different paths through the communications infrastructure are different, cause the server infrastructure system to perform operations comprising:
- receiving each of a plurality of gateway timestamp-attached data transaction request packets from a plurality of gateway infrastructure systems via the communication infrastructure, wherein a respective gateway timestamp is attached to each gateway timestamp-attached data transaction request packet, the respective gateway timestamp corresponds to either a time at which a respective corresponding incoming data transaction request packet is in the gateway infrastructure system or in a network device located between the gateway infrastructure system and a client computer system from the one or more client computer systems from which the respective corresponding incoming data transaction request packet originated;
- for each of the gateway timestamp-attached data transaction request packets:
- attaching a server timestamp to the gateway timestamp-attached data transaction request packet, the server timestamp corresponding to a time at which the gateway timestamp-attached data transaction request packet is in the server infrastructure system;
- determining a transaction delay based upon the gateway timestamp and the server timestamp attached to the server timestamp-attached data transaction request packet;
- comparing the transaction delay to a preset threshold time interval, and:
- if the transaction delay is less than the preset threshold time interval, assigning, using the flush timer, a respective flush time to the gateway timestamp-attached data transaction request packet and insert the gateway timestamp-attached transaction request packet into the reorder buffer;
- or
- if the transaction delay is not less than the preset threshold time interval, outputting the gateway timestamp-attached data transaction request packet to a data processing application without storing the gateway timestamp-attached data transaction request packet in the reorder buffer;
- reordering, using the reorder buffer, the server timestamp-attached data transaction request packets in order of oldest to newest of the respective gateway timestamps of the server timestamp-attached data transaction request packets, wherein the reordering is based on both the gateway timestamp and the server timestamp of respective ones of the server timestamp-attached data transaction request packets;
- and
- outputting the reordered server timestamp-attached data transaction request packets from the reorder buffer in an order of oldest to newest of the respective gateway timestamps and in accordance with the respective associated flush times, via a shared memory pipe, to the data processing application, wherein the data processing application is configured to process the data transaction request packets in order of receipt at the data processing application;
- wherein the server infrastructure system is configured to perform the reordering and the outputting such that the output server timestamp-attached data transaction request packets are received by the data processing application in order of arrival at the plurality of gateway infrastructure systems, even if the corresponding gateway timestamp-attached transaction request packets arrived out of order at the server infrastructure due to the different packet latencies and jitter in the communication infrastructure between the plurality of gateway infrastructure systems and the server infrastructure system.
9 more elements
Dependencies are inferred from the claim text.