Data compression engine

Patent metadata

Field	Value
Publication number	US-12574448-B2
Application number	US-202318200074-A
Country	US
Kind code	B2
Filing date	May 22, 2023
Priority date	Jun 30, 2022
Publication date	Mar 10, 2026
Grant date	Mar 10, 2026

Abstract

Compressing connection state information for a network connection including receiving an input bitmap having a sequence of bits describing transmit states and receive states; partitioning the input bitmap into a plurality of equal size blocks; partitioning each of the blocks into a plurality of equal sized sectors; generating a block valid sequence indicating the blocks having at least one bit set; generating, for each block having at least one bit set, a sector information sequence, the sector information sequence indicating, for the corresponding block, the sectors that have at least one bit set and an encoding type for each sector; and generating one or more symbols by encoding each sector that has at least one bit set.

First claim

The invention claimed is:

1 . A method for compressing connection state information comprising:
receiving an input bitmap comprising a sequence of bits describing transmit states and receive states for packets in a connection between a first node on a network and a second node on the network, each bit in the sequence of bits being either set or unset; partitioning the input bitmap into a plurality of equal size blocks; partitioning each of the blocks into a plurality of equal sized sectors; generating a block valid sequence indicating the blocks having at least one bit set; generating, for a block of the plurality of equal size blocks having at least one bit set, a sector information sequence, the sector information sequence indicating, for the block of the plurality of equal size blocks, the sectors that have at least one bit set and an encoding type for each sector; and generating one or more symbols by encoding each sector that has at least one bit set, according to the encoding type for the sector, such that each encoded sector corresponds to one of the symbols, wherein the input bitmap is a concatenation of bitmaps, and wherein the bitmaps include a transmitter request window bitmap, a transmitter data window bitmap, a receiver request window bitmap, a receiver data received window bitmap, and a receiver data received and acknowledged window bitmap.

2 . The method according to claim 1 , wherein the encoding type for each sector is one of a raw type or a run length encoding type.

3 . The method according to claim 2 , wherein the encoding type for a sector is the run length encoding type only when there is a single run of bits set in the sector.

4 . The method according to claim 3 , wherein when a sector is encoded according to the run length encoding type, the symbol for the encoded sector comprises a start offset indicating a bit position for a first bit of the single run, and an end offset indicating a bit position for a last bit of the single run.

5 . The method according to claim 1 , further comprising a step of forming a compressed vector by concatenating the block valid sequence, the sector information sequences, and the one or more symbols.

6 . The method according to claim 5 , further comprising storing the compressed vector.

7 . A system for compressing connection state information comprising:
at least one processor for controlling
receiving an input bitmap comprising a sequence of bits describing transmit states and receive states for packets in a connection between a first node on a network and a second node on the network, each bit in the sequence of bits being either set or unset;
partitioning the input bitmap into a plurality of equal size blocks;
partitioning each of the blocks into a plurality of equal sized sectors;
generating a block valid sequence indicating the blocks having at least one bit set;
generating, for a block of the plurality of equal size blocks having at least one bit set, a sector information sequence, the sector information sequence indicating, for the block of the plurality of equal size blocks, the sectors that have at least one bit set and an encoding type for each sector; and
generating one or more symbols by encoding each sector that has at least one bit set, according to the encoding type for the sector, such that each encoded sector corresponds to one of the symbols,
wherein the input bitmap is a concatenation of bitmaps, and
wherein the bitmaps include a transmitter request window bitmap, a transmitter data window bitmap, a receiver request window bitmap, a receiver data received window bitmap, and a receiver data received and acknowledged window bitmap.

8 . The system according to claim 7 , wherein the encoding type for each sector is one of a raw type or a run length encoding type.

9 . The system according to claim 8 , wherein the encoding type for a sector is the run length encoding type only when there is a single run of bits set in the sector.

10 . The system according to claim 9 , wherein when a sector is encoded according to the run length encoding type, the symbol for the encoded sector comprises a start offset indicating a bit position for a first bit of the single run, and an end offset indicating a bit position for a last bit of the single run.

11 . The system according to claim 7 , wherein the at least one processor is further operable to control forming a compressed vector by concatenating the block valid sequence, the sector information sequences, and the one or more symbols.

12 . The system according to claim 11 , wherein the at least one processor is further operable to control storage of the compressed vector.

13 . The system according to claim 7 , further comprising a compression interface for receiving the input bitmap and for receiving an indication that the input bitmap is valid.

14 . The system according to claim 7 , further comprising an interface for receiving the input bitmap and for providing an indication of a total number of bits in the symbols.

15 . The system according to claim 7 , wherein the at least one processor is further operable to perform decompression on the symbols.

16 . The system according to claim 15 , wherein
the at least one processor is further operable to control forming a compressed vector by concatenating the block valid sequence, the sector information sequences, and the one or more symbols, and the system further comprises a decompression interface for outputting the compressed vector and an indication that the compressed vector is valid.

Assignees

• Google Llc

Inventors

• Vaduvatha Srinivas
• Jiang Weiwei
• Chandra Prashant
• Oladipo Opeoluwa
• Zheng Jiazhen
• Walsh Hugh Mcevoy
• Wang Weihuang
• Agarwal Abhishek

Classifications

• H03M7/48

  alternating with other codes during the code conversion process, e.g. run-length coding being performed only as long as sufficientlylong runs of digits of the same kind are present · CPC title

• H03M7/70

  Type of the data to be coded, other than image and sound · CPC title

• H03M7/6011

  Encoder aspects · CPC title

• H04L69/04 Primary

  Protocols for data compression, e.g. ROHC · CPC title

• H03M7/3066 Primary

  by means of a mask or a bit-map · CPC title