Search Unity

Questions about packet compression (Huffman Stream)

Discussion in 'FPS.Sample Game' started by Kichang-Kim, Nov 1, 2018.

  1. Kichang-Kim

    Kichang-Kim

    Joined:
    Oct 19, 2010
    Posts:
    424
    Hi, I checked FPSSample and thanks for this great sample.

    I have some questions about packet compression, especially HuffmanInputStream / HuffmanOutputStream.

    My basic understanding for Huffman encoding is here:
    1. Calculate symbol probability distribution of input data
    2. Construct binary-tree and generate symbol-code table by using it
    3. Encode input data using symbol-code table

    And here is my questions:
    1. Is this true that NetworkCompressionModel uses pre-defined symbol-code table? It seems that there is no code for calculating table from actual data.
    2. What are the roles of these variables? :
    NetworkCompressionConstants.k_BucketOffsets
    NetworkCompressionConstants.k_BucketSizes
    "int context" argument of every read/write method

    Thanks.
     
  2. stubbesaurus

    stubbesaurus

    Unity Technologies

    Joined:
    Oct 7, 2016
    Posts:
    3
    Hi,

    Things got a little hectic up to Unite, but we definitely want to revisit this code and document it.

    It seems your basic understanding of Huffman is correct. Symbols are coded using a variable number of bits based on their expected frequency to minimize the expected number of bits needing to be sent.

    1. The default is to use a pre-defined symbol-code table, but there is functionality to generate a model from statistics. NetworkCompressionCapture is a helper class that you can pipe network traffic into and then call AnalyzeAndGenerateModel on to obtail a serialized huffman model that you can use to construct a NetworkCompressionModel specifically for that type of traffic.

    This functionality is also exposed through the console, where 'beginnetworkprofile' starts a recording session, 'endnetworkprofile myfile' ends the recording session and stores the model to a file and finally 'loadcompressionmodel myfile' can be used on the server to load and use a model. Clients connecting after the model has been loaded will receive and use this model as they connect.

    2. When you send something like an 32bit integer over the network, it is impractical to create a huffman tree that encompasses every possible value the integer can take as it would require a tree with 2^32 leaves! To make this more practical we lump values into a managable number of power-of-two-sized buckets and then only code the bucket index with Huffman and code the position in the bucket using a number of raw bits corresponding to the size of the bucket. The buckets are arranged so they are small around 0 and become progressively larger as you move away from zero. The rationale is that as most data is deltas against predictions, we expect values to be small and generally expect most of the redundancy to be in the size of the error and not in exactly which of the values of that size we end up hitting.

    NetworkCompressionConstants.k_BucketSizes specifies the sizes of the buckets in bits, so a bucket of n bits has 2^n values.
    NetworkCompressionConstants.k_BucketOffsets specifies the starting positions of the bucket.

    Bucket n starts at k_BucketOffsets[n] and ends at k_BucketOffsets[n] + (1 << k_BucketSizes[n]).

    The context can be throught of as a submodel that has it's own statistics and uses its own huffman tree. The context used to read and write a specific value must always be the same. The benefit of using multiple contexts is that it allows you to separate the statistics of things that have different expected distributions, which leads to more precise statistics, which again yields better compression. For example FPS sample assigns unique contexts to all fields of all property sheet. More contexts does however result in a marginal cost of a slightly larger model.

    I hope this is helpful.
     
    Enzi and Kichang-Kim like this.
  3. Kichang-Kim

    Kichang-Kim

    Joined:
    Oct 19, 2010
    Posts:
    424
    Thanks for detailed explanation!
     
unityunity