Method and system for reducing network latency in data communication

• US 20030110296A1
• Filed: 12/07/2001
• Published: 06/12/2003
• Est. Priority Date: 12/07/2001
• Status: Active Grant

• Current Assignee: Propel Software Corporation (Apple Inc.)
• Original Assignee: Propel Software Corporation (Apple Inc.)
• Inventors: Kirsch, Steven T., Murray, David J.
• Granted Patent: US 7,370,120 B2
• Time in Patent Office: Days
• US Class Current: 709/246
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/561 Adding application-functional data or data for application control, e.g. adding metadata
• CPC Class Codes: H04L 67/5651 Reducing the amount or size of exchanged application data
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Methods and systems for accelerating data communication by reducing network latency particularly by data compression in which requested data is recursively compressed by an encoder and sent to the requester in codes which may or may not be understood by the requester. The requester can subsequently request data corresponding to unknown codes. The request-reply sequence is also recursive and continues until the requested data is present at the requester. To further accelerate communication, a persistently connected network is employed, together with a new socket layer capable of combining multiple messages from different machines, threads, and/or processes into single TCP/IP packets to be relayed along message hubs in the persistent network. These features are introduced singly and combined to create a new caching network. A new content distribution network can take advantage of these data communication improvements since requested content can be distributed in caches in a caching network.

Claims

1. In a communications network having a plurality of devices which are located at different network nodes, a method of communicating data between devices in an accelerated manner, said method comprising:

a) compressing data with software acting as an encoder, said software running on a first device in network communication with other devices, said compressed data to be transmitted to a second device in the network running software acting as a decoder, said compressing consisting of representing runs of data with at least one identifier;

b) storing said at least one identifier and corresponding data represented by said at least one identifier in a database associated with said encoder;

c) transmitting from the encoder to the decoder data corresponding to the identifier only when said data is specifically requested by the decoder.

2. The method of claim 1 further including representing runs of identifiers with a single identifier.

3. The method of claim 1 further including representing runs of identifiers and data with a single identifier.

4. The method of claim 2 further defined by using a single identifier to represent runs of identifiers, the use of the single identifier determined by relative frequency of occurrence of adjacency of the identifiers over a range of transmitted data.

5. The method of claim 3 further defined by using a single identifier to represent runs of identifiers and text, the use of the single identifier determined by relative frequency of occurrence of adjacency of the identifiers and data over a range of transmitted data.

6. The method of claim 2 wherein said single identifier may represent a linear sequence of identifiers and data.

7. The method of claim 3 wherein said single identifier may represent a linear sequence of identifiers and data.

8. The method of claim 2 further defined by using a single identifier to represent a run of identifiers, the use of the single identifier determined by whether the run of identifiers has recently occurred.

9. The method of claim 3 further defined by using a single identifier to represent a run of identifiers and data, the use of the single identifier determined by whether the run of identifiers has recently occurred.

10. The method of claim 1 further defined by the decoder initiating a round trip request for corresponding data for specific identifiers not contained in a database associated with the decoder from the encoder, said round trip request including a request from the decoder for said corresponding data and a reply to said request from the encoder.

11. The method of claim 1 further defined by the decoder initiating more than one round trip request for data corresponding to unknown identifiers to the encoder.

12. The method of claim 2 further defined by compressing runs of single identifiers with yet another identifier.

13. The method of claim 3 further defined by compressing runs of single identifiers with yet another identifier.

14. The method of claim 1 further defined by decompressing at the encoder at least a portion of the data to be transmitted when the database associated with the encoder has no recently generated record of the identifier generated by the compressing step.

15. The method of claim 2 wherein said runs of data may represent at least one line of text.

16. The method of claim 1 wherein identifiers are assigned by breaking up the data to be encoded in chunks.

17. The method of claim 16 wherein the type of data to be compressed determines how the data is broken into chunks.

18. The method of claim 1 wherein determining which runs of data are to be represented by an identifier is based on whether that data has been previously seen by the encoder.

19. The method of claim 1 wherein determining which runs of data are to be represented by an identifier is based on whether that data has been previously transmitted by the encoder.

20. The method of claim 1 wherein determining which runs of data are to be represented by an identifier is based on whether that data is likely to be found in a cache at the decoder.

21. The method of claim 1 wherein determining which runs of data are to be represented by an identifier is based on whether that data is likely to be found in a cache at an intermediate relay hub in the network.

22. The method of claim 1 further defined by creating an identifier for a page template used to assemble a page containing dynamic data.

23. The method of claim 22 further defined by creating at least one identifier for dynamic data to populate said page template.

24. The method of claim 1 further defined by decompressing at the encoder at least a portion of the data to be transmitted when the database associated with the encoder has no recently generated record of the identifier generated by the compressing step.

25. The method of claim 24 further defined by using a known compression scheme to compress decompressed data.

26. In a communications network having a plurality of devices which are located at different network nodes, a method of communicating data between devices in an accelerated manner, said method comprising:

a) compressing data with software acting as an encoder, said software running on a first device in network communication with other devices, said compressed data to be transmitted to a second device in the network running software acting as a decoder, said compressing consisting of representing runs of data with at least one identifier;

b) storing said at least one identifier and corresponding data represented by said at least one identifier in a database associated with said encoder,

c) determining whether there are any runs of identifiers in compressed data;

d) representing runs of identifiers in compressed data with a single identifier, thereby achieving further compression of said data;

e) storing said single identifier and corresponding runs of identifiers represented by single identifier in the database associated with said encoder; and

f) transmitting from the encoder to the decoder data corresponding to an identifier only when said data is specifically requested by the decoder.

27. The method of claim 26 wherein the single identifier is not used to represent a run of identifiers if the database associated with the encoder has no recently generated record of the run of identifiers.

28. The method of claim 26 wherein identifiers are assigned by breaking up the data to be compressed in chunks.

29. The method of claim 28 wherein the type of data to be compressed determines how the data is broken into chunks.

39. The method of claim 26 further defined by transmitting identifiers to the second device as soon as they are generated.

40. The method of claim 27 further defined by transmitting identifiers to the second device as soon as they are generated.

41. The method of claim 28 further defined by transmitting identifiers to the second device as soon as they are generated.

42. The method of claim 26 further defined by breaking data into segments, generating a single identifier for each segment, and transmitting each identifier as it is generated, wherein a large amount of data is transmitted incrementally as each segment is encoded.

30. In a communications network having a plurality of devices which are located at different network nodes, a method of communicating data between devices, said method comprising:

a) breaking up data to be compressed and transmitted to a second device at a first device, said data broken up into logical segments according to data type;

b) compressing data by representing segments of data with at least one identifier;

c) transmitting said at least one identifier when data is requested by the second device; and

d) at the second device looking up the identifier and producing associated data for a known identifier and for an unknown identifier, requesting data associated with said unknown identifier, whereby the requested data enables decompression of the compressed data.

31. The method of claim 30 further defined by generating a plurality of identifiers at the second device and then replacing some of the plurality of identifiers with a single identifier.

32. The method of claim 31 further defined by recursively replacing identifiers with a single identifier.

33. The method of claim 31 further defined by using the same identifier to represent a run or data that has been seen before.

34. The method of claim 32 further defined by recursively encoding data and generating a single identifier representing the data.

35. The method of claim 30 further defined by using software acting as an encoder for the breaking up and compression of data at the first device.

36. The method of claim 35 further defined by using software acting as a decoder for decompressing data at the second device.

37. The method of claim 36 further defined by the decoder recursively requesting data associated with unknown identifiers by requesting them from the encoder.

38. The method of claim 33 further defined by the decoder receiving data associated with unknown identifiers from another device intermediating between the first and second device in the network, said another device having cached data associated with unknown identifiers.

43. In a communications network having a plurality of devices which are located at different network nodes, a method of communicating data between devices in an accelerated manner, said method comprising:

a) compressing data with software acting as an encoder, said software running on a first device in network communication with a other devices, said compressed data to be transmitted to a second device in the network running software acting as a decoder, said compressing consisting of breaking up data at predetermined points to create runs of data and representing said runs of data with at least one identifier, thereby achieving compression of said data; and

b) storing said at least one identifier and corresponding data represented by said at least one identifier in a database associated with said encoder,

c) transmitting from the encoder to the decoder data corresponding to the identifier only when said data is specifically requested by the decoder.

44. The method of claim 43 further defined by breaking up the data at a line break.

45. The method of claim 43 further defined by breaking up the data at a paragraph break.

46. The method of claim 43 wherein identifiers are assigned by breaking up the data to be compressed in chunks.

47. The method of claim 46 wherein the type of data to be compressed determines how the data is broken into chunks.

48. In a communications network having a plurality of devices which are located at different network nodes, a method of communicating data between devices in an accelerated manner, said method comprising:

a) compressing data with software acting as an encoder, said software running on a first device in network communication with other devices, said compressed data to be transmitted to a second device in the network running software acting as a decoder, said compressing consisting of representing runs of data with at least one identifier;

b) storing said at least one identifier and corresponding data represented by said at least one identifier in a database associated with said encoder;

c) repeating steps a) and b) as necessary to achieve a desired level of compression; and

d) transmitting from the encoder to the decoder data corresponding to the identifier only when said data is specifically requested by the decoder.

49. The method of claim 48 further including representing runs of identifiers with a single identifier.

50. The method of claim 48 further including representing runs of identifiers and data with a single identifier.

51. The method of claim 49 further defined by using a single identifier to represent runs of identifiers, the use of the single identifier determined by relative frequency of occurrence of adjacency of the identifiers over a range of transmitted data.

52. The method of claim 51 further defined by using a single identifier to represent runs of identifiers and text, the use of the single identifier determined by relative frequency of occurrence of the identifiers and text over a range of transmitted data.

53. The method of claim 49 wherein said single identifier may represent a linear sequence of identifiers and data.

54. The method of claim 50 wherein said single identifier may represent a linear sequence of identifiers and data.

55. The method of claim 48 further defined by using a single identifier to represent a run of identifiers, the use of the single identifier determined by whether the run of identifiers has recently occurred.

56. The method of claim 50 further defined by using a single identifier to represent a run of identifiers and data, the use of the single identifier determined by whether the run of identifiers has recently occurred.

57. The method of claim 48 further defined by the decoder initiating a round trip request for corresponding data for specific identifiers not contained in a database associated with the decoder from the encoder, said round trip request including a request from the decoder for said corresponding data and a reply to said request from the encoder.

58. The method of claim 48 further defined by the decoder initiating more than one round trip request for data corresponding to unknown identifiers to the encoder.

59. The method of claim 49 further defined by encoding runs of single identifiers with yet another identifier.

60. The method of claim 50 further defined by encoding runs of single identifiers with yet another identifier.

61. The method of claim 48 further defined by decompressing at the encoder at least a portion of the data to be transmitted when the database associated with the encoder has no recently generated record of the identifier generated by the compressing step.

62. The method of claim 48 wherein said runs of data may represent at least one line of text.

63. The method of claim 48 wherein identifiers are assigned by breaking up the data to be compressed in chunks.

64. The method of claim 63 wherein the type of data to be compressed determines how the data is broken into chunks.

65. In a communications network, a method for decoding data at a client running software acting as a decoder wherein the client has previously requested data from a server running software acting as a encoder, said method comprising:

a) receiving at the decoder an encoded reply from the server, said encoded reply having identifiers corresponding to data in the reply;

b) determining whether a database associated with the decoder recognizes identifiers present in the encoded reply;

c) sending another request from the decoder to the encoder for data corresponding to unrecognized identifiers not present in the decoder'"'"'s database;

d) sending requested data corresponding to unrecognized identifiers from the encoder to the decoder;

e) repeating steps c) and d) if necessary; and

f) assembling the reply from the data at the decoder.

66. In a communications network, a method for decoding data at a client running software acting as a decoder wherein the client has previously requested data from a server running software acting as a decoder, said method comprising:

a) receiving at the decoder an encoded reply from the server, said encoded reply having identifiers corresponding to data in the reply;

b) sending a further request to the encoder for data corresponding to identifiers not recognized by a database associated with the decoder;

c) receiving a reply to the further request at the decoder;

d) repeating steps b) and c) if necessary; and

f) assembling the first reply from the data with the decoder.

67. In a communications network having a plurality of devices which are located at different network nodes, a system for communicating data between devices in an accelerated manner, said system comprising:

a) an encoder having means for compressing data by representing runs of data with at least one identifier and storing said at least one identifier and corresponding data represented by said at least one identifier in a database associated with encoder, said encoder running on a first device in network communication with other devices, said compressed data to be transmitted to a second device in the network, said encoder running on a first device in network communication with other devices; and

b) a decoder having means for decompressing compressed data received from the encoder by determining whether said at least one identifier in the compressed data is contained in a second database associated with the decoder and requesting data corresponding to an unknown identifier from the encoder, said decoder running on a second device in network communication with other devices.

68. The system of claim 67 wherein the encoder is running on a server.

69. The system of claim 67 wherein the encoder is running on a machine intermediating between a client and a server.

70. The system of claim 67 wherein the decoder is running on a client.

71. The system of claim 67 further defined by the encoder having the means to recursively compress data.

72. The system of claim 71 further defined by the decoder having the means to initiate at least one round trip request for data corresponding to unknown identifiers not contained in the database associated with the decoder from the encoder, said round trip request including a request from the decoder for said corresponding data and a reply to said request from the encoder.

73. In a communications system, a method for transmitting data requested by a client from a server in an accelerated manner, said method comprising:

a) receiving at a server running software acting as an encoder a request for data from a client running software acting as a decoder;

b) compressing with the encoder portions of a reply to the request known to the encoder by representing said portions of the reply with at least one identifier;

c) caching the at least one identifier and corresponding data in a database associated with the encoder; and

d) returning the reply to the client, wherein the decoder decompresses the reply and assembles the data.

74. The method of claim 73 further including the decoder looking up at least one identifier contained in the reply in a database associated with the decoder.

75. The method of claim 74 further including the decoder requesting data from the encoder for any identifier not contained in the decoder'"'"'s database.

76. The method of claim 75 further including the decoder initiating more than one round trip request for data corresponding to unknown identifiers not contained in a database associated with the decoder from the encoder, said round trip request including a request from the decoder for said corresponding data and a reply to said request from the encoder.

77. The method of claim 75 further including a second encoder running at a second server intermediating between the first server and the client filling the decoder'"'"'s request for data corresponding to any identifier not found in the decoder'"'"'s database.

78. The method of claim 73 wherein an encoding technique includes creating an identifier for portions of the text.

79. The method of claim 78 further including creating a new identifier to represent runs of previously generated identifier.

80. The method of claim 73 wherein the client and server are members of a persistent network having a plurality of hubs, each hub connected another hub by a dedicated socket connection, wherein there is bi-directional asynchronous communication between dedicated socket pairs of network hubs.

81. The method of claim 73 wherein the encoder compares the identifier of a new reply from a server with the identifier of a reply to the same request cached in the database to determine whether the data content of the cached reply differs from the new reply.

82. The method of claim 81 wherein the encoder sends the cached reply if the content of the two replies is identical.

83. The method of claim 81 wherein the encoder determines the existence of a data content update pattern for frequently requested data.

84. The method of claim 86 wherein at least one member of the network contains a database for caching identifiers and corresponding data of encoded replies relayed to a requester by said member.

85. The method of claim 84 wherein a member of the network intermediating between a client and a server creates a reply to the client'"'"'s request for data directed to the server from encoded replies contained in the intermediating member'"'"'s database.

86. The method of claim 73 wherein the encoder over time detects runs of identifiers between encoded replies to similar requests for data.

87. The method of claim 86 wherein the encoder further compresses runs of identifiers.

88. In a communications system, a method for encoding and transmitting data requested by a client from a server, said method comprising:

a) receiving at a server running software acting as an encoder a request for data from a client running software acting as a decoder;

b) encoding with the encoder a reply to said request,

c) returning the reply to the client;

d) receiving the reply at the client;

e) determining with decoder whether a database stored at the client contains data corresponding to identifiers sent by the encoder such that the entire reply can be decoded and assembled;

f) requesting the encoder to send data strings corresponding to any identifiers contained in the reply which are not stored in a database at the client;

g) receiving said request at the encoder;

h) returning the requested data to the client;

i) repeating steps e)-h) if necessary;

j) decoding the request at the client; and

k) assembling the requested data at the client.

89. The method of claim 91 further including the encoded reply consisting of one of a series of:

a) at least one identifier corresponding to strings of data known to the encoder, said at least one identifier created by the encoder and stored in a database associated with the encoder;

b) at least one identifier corresponding to strings of data known to the encoder and unencoded data corresponding to dynamic portions of the requested data, said at least one identifier created by the encoder and stored in a database associated with the encoder; and

c) unencoded data that is unique in its entirety to the encoder.

90. The method of claim 88 wherein an encoding technique includes creating a hash code for portions of the data.

91. The method of claim 88 wherein the client and server are members of a persistent network having a plurality of hubs, each hub connected to another hub by a dedicated socket connection, wherein there is bi-directional asynchronous communication between dedicated socket pairs of network hubs.

92. The method of claim 88 wherein the encoder compares a new reply from a server with a reply to the same request cached in the database to determine how the data content of the cached reply the differs from the new reply.

93. The method of claim 92 wherein the encoder determines the existence of a data content update pattern for frequently requested data.

94. The method of claim 91 wherein each member of the network contains a database for caching identifiers and corresponding data of encoded replies relayed to a requester by said member.

95. The method of claim 94 wherein a member of the network intermediating between a client and a server creates a reply to the client'"'"'s request for data directed to the server from encoded replies contained in the intermediating member'"'"'s database.

96. The method of claim 88 wherein the encoder over time detects runs of identifiers between encoded replies to identical requests for data.

97. The method of claim 96 wherein the encoder further encodes runs of identifiers.

98. In a communications system, a method for transmitting data requested by a client from a server in an accelerated manner, said method comprising:

a) receiving at a server a request for data from a client running software acting as a decoder;

b) sending a reply from the server to an intermediate device running software acting an encoder, said intermediate machine in network connection with the server and the client;

c) compressing the reply with the encoder said compressing consisting of representing runs of data with at least one identifier;

d) caching the at least one identifier and corresponding data in a database associated with the encoder; and

e) returning the reply to the client, wherein the decoder decompresses the reply and assembles the data.

99. The method of claim 98 further including the decoder looking up identifiers contained in the reply in a database associated with the decoder.

100. The method of claim 98 further including the decoder requesting data from the encoder for identifiers not contained in the decoder'"'"'s database.

101. The method of claim 98 wherein an encoding technique includes creating a hash code for representing portions of the data.

102. The method of claim 98 wherein the client and server are members of a network having a plurality of hubs, each hub connected to another hub by a socket connection, wherein there is bi-directional asynchronous communication between dedicated socket pairs of network hubs.

103. The method of claim 98 wherein the encoder compares a new reply from a server with a reply to the same request cached in the database to determine whether the data content of the cached reply differs from the new reply.

104. The method of claim 103 wherein the encoder determines the existence of a data content update pattern for frequently requested data.

105. The method of claim 102 wherein at least one member of the network contains a database for caching identifiers and corresponding data of encoded replies relayed to a requester by said member.

106. The method of claim 105 wherein a member of the network intermediating between a client and a server creates a reply to the client'"'"'s request for data directed to the server from information contained in the intermediating member'"'"'s database.

107. The method of claim 98 wherein the encoder over time detects runs of identifiers between encoded replies to identical requests for data.

108. The method of claim 107 wherein the encoder further encodes runs of identifiers.

109. In a communications network containing a plurality of network hubs, a method of communicating data between an encoder and a decoder comprising:

a) encoding data to be transmitted to a decoder, said encoded data containing at least one identifier, said at least one identifier and data corresponding to said at least one identifier stored in a first database associated with an encoder;

b) establishing a second database at the decoder having a plurality of identifiers and data corresponding to said plurality of identifiers;

c) receiving a request for encoded data, said request sent by the decoder;

d) determining whether any identifiers contained in requested data are known to the decoder; and

e) transmitting requested, encoded data and data corresponding to any identifier not contained in the second database to the decoder.

110. The method of claim 109 further including data corresponding to any identifier not contained in the second database being delivered to the decoder by at least one network hub intermediating between the decoder and encoder, said network hub having a database containing the data corresponding to the unknown identifier.

111. The method of claim 109 further including using a known compression scheme to compress data corresponding to any identifier not contained in the second database before transmitting said data to the decoder.

112. The method of claim 109 further including the decoder specifically requesting data corresponding to any unknown identifier from the encoder.

113. The method of claim 109 further including sending data corresponding to an identifier to the decoder if said identifier was previously unknown to the encoder.

114. In a communications network, a method of communicating data between an encoder and a decoder, said method comprising:

a) sending a request from a decoder to an encoder, said request including an identifier representing requested data previously sent to the decoder;

b) determining whether the requested data corresponds to the identifier sent by the decoder;

c) sending an encoded reply to the requested data from the encoder to the decoder if the requested data has been updated, otherwise sending a confirmation that the identifier sent by the decoder corresponds to the requested data.

115. The method of claim 114 further including assembling requested data at the decoder.

116. The method of claim 114 further including the decoder requesting data corresponding to any unknown identifiers in the encoded reply.

117. The method of claim 114 further including compressing data in the encoded reply using a known compression scheme before sending said data to the decoder.

118. The method of claim 116 further including assembling requested data at the decoder.

119. A method of compressing data to be communicated in a network, said method comprising:

a) breaking up data to be compressed into logical segments according to data type;

b) storing said at least one identifier and data corresponding to said at least one identifier in a database;

c) detecting runs of identifiers in compressed data;

d) representing runs of identifiers in compressed data;

e) storing said another identifier in said database; and

f) repeating steps d)-e) as necessary to achieve desired level of compression.

120. The method of claim 119 further including maintaining a table for each server containing data that is compressed, wherein said table includes any identifier generated and information about identifiers preceding or following any given identifier.

121. The method of claim 120 further including determining a first identifier is part of a run of data when the table indicates said first identifier has a second identifier preceding the first identifier and a third identifier following the first identifier.

122. The method of claim 121 further including ignoring certain common identifiers to determine whether a first identifier has other identifiers adjacent to the first identifier.

123. The method of claim 119 wherein a known compression method is used to detect runs of identifiers.

124. In a communications network where compressed data is exchanged between members of the network, a method of efficiently communicating compressed data, said method comprising:

a) receiving compressed data, said data compressed by representing each segment of data with an identifier, said identifier and data corresponding to said identifier stored in a first database associated with compression software;

b) storing received identifiers and data corresponding to said identifiers in a second database associated with decompression software;

c) requesting data that contains a subset of data previously received, wherein identifiers and data are contained in the second database;

d) receiving an identifier in reply to said request, said identifier including;

i) a code identifying a set of data contained in the second database;

ii) a second code identifying a starting offset, said offset indicating where the requested data may be found in the set of data contained in the second database;

iii) a third code identifying a length, said length indicating an end point of the requested data contained in the second database; and

e) assembling the requested data from the reply and the data contained in the second database.