[Freeciv-Dev] [RFC][Patch] Reduce bandwith by using deltas

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

Per mentioned on IRC that certain fields in the player struct don't
change (name, nation). And also the team and team_name if the team
patch is applied. We also suspected for a long time that for example
only a certain set of fields change for each city during
turn-change. These include the food-stock and the shield-stock. So I
spent yesterday to some analysis and came up with a patch.

The idea is simple: instead of transferring all fields for a given
foo-info only the fields which have been changed are
transferred. However you need to specify which fields have
changed. This requires one bit for each field. These bits have to be
send in all cases. Another extra overhead is required: to be
transparent wrt to the upper layers the data for the previous state of
this object is required. Same is true for the sending side because
this side must decide which fields have changed. If both side have no
information about the object they have to transfer all fields. But
wait it be optimized further: add default values for the fields. This
is currently done by using the value '\0' as default for all
fields. This will for example save a huge amount of the special fields
in the tile_info object. If no field of a object has changed the
packet is discarded (nothing at all is send).

It turns out that the implementation is straightforward but requires
written a lot of code. So I decided to go for a generator system
similar to create_lsend.pl. The input looks like this:

packet_tile_info PACKET_TILE_INFO
        x, int , uint8, key
        y, int , uint8, key

        type, int, uint8
        special, int, uint16
        known, int, uint8
end

Out of this input the following is created:
 - the actual struct packet_tile_info:

 {
  int x;
  int y;
  int type;
  int special;
  int known;
};

 - two functions for the hash table: hash_packet_tile_info and
 cmp_packet_tile_info. For these the "key" from above is important.

 - a definition for the bitfield of the fields:
 BV_DEFINE(packet_tile_info_fields, 3);

 - the actual send_packet_tile_info and receive_packet_tile_info
 functions. Both have the same interface as the current ones.

 - some code to help analysing which fields have changed in report()

This delta-protocol is only possible for info packets. So for example
you don't want that your attack command is discarded because it looks
like the previous one. This is also the reason for the naming
packets_info*. Currently I have transformed packet_tile_info,
packet_unit_info, packet_game_info, packet_city_info and
packet_player_info. I.e. the ones with the highest bandwidth usage in
the past.

The generator script is written in python. I could have used perl but
then it would have required multiple days to write it. Feel free to
convert it. The generated packets_info.c has currently 2700
lines. This is a bit more than the packets.c file. So it was a good
idea to use a generator (420 lines).

Results: halve of the packet_tile_info, packet_unit_info and
packet_city_info packets could be discarded. This means a reduction to
50%. In the remaining halve also a lot can be saved:

2: packet_tile_info 3244 out of 6817 got discarded
2:   3412 / 3573:  0 = type
2:    597 / 3573:  1 = special
2:   3246 / 3573:  2 = known

So only in 597 of the 3573 cases where actually data was send the
special field was transfered. You also see that certain fields are (as
expected) (almost) constant zero:

2: packet_unit_info 68 out of 178 got discarded
2:     10 /  110:  0 = owner
2:     77 /  110:  1 = x
2:     80 /  110:  2 = y
...

2:     85 /  110:  8 = activity
2:     90 /  110:  9 = activity_count

activity and activity_count are the ones which create the most traffic
for the units. And in this data this issues is already. Normally the
numbers are even higher.

2:      0 /  110: 10 = unhappiness
2:     73 /  110: 11 = upkeep
2:     14 /  110: 12 = upkeep_food

2:      0 /  110: 13 = upkeep_gold

We have no gold upkeep.

2:      0 /  110: 18 = activity_target
2:      0 /  110: 19 = paradropped
2:      0 /  110: 20 = connecting
2:      0 /  110: 21 = carried
2:      0 /  110: 22 = select_it
2:      0 /  110: 23 = packet_use
2:      0 /  110: 24 = info_city_id
2:      0 /  110: 25 = serial_num

Old data:
> 2:   [ 5]:   6826 packets;   197954 bytes total;    29 bytes/packet average 
> PACKET_UNIT_INFO
> 2:   [ 9]:  13114 packets;   118026 bytes total;     9 bytes/packet average 
> PACKET_TILE_INFO
> 2:   [13]:    163 packets;    74196 bytes total;   455 bytes/packet average 
> PACKET_PLAYER_INFO
> 2:   [17]:   5123 packets;   567459 bytes total;   110 bytes/packet average 
> PACKET_CITY_INFO

New data:
2:   [ 5]:    266 packets;     3659 bytes total;    13 bytes/packet average
2:   [ 9]:   3580 packets;    29342 bytes total;     8 bytes/packet average
2:   [13]:     13 packets;     3170 bytes total;   243 bytes/packet average
2:   [17]:    290 packets;     9962 bytes total;    34 bytes/packet average

While these aren't the same situations it is visibile that the
bytes/packet is reduced to a half or a third.

I have done my data gathering only by loading a game and pressing
turn-done some times. This is bad. It would be nice if anyone can
provide me with data from some real games.

The patch breaks the network completely. Also since the code is
generated the ability to add/remove fields isn't there. Looks like
some condition has to be added to the input description.

I will address the changes I have made to the other files in seperate
mails.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 checking for the vaidity of the Maxwell laws on this machine... ok
 checking if e=mc^2... ok
 checking if we can safely swap on /dev/fd0... yes
    -- kvirc 2.0.0's configure

delta1.diff.gz
Description: application/gunzip