Gaps in IceTV EPG

There has been a longstanding issue of occasional gaps showing in the IceTV EPG on Beyonwiz and not on other devices using the new IceTV servers.

It boils down to the Birthday Problem (and is similar to the Birthday Attack) (see, for example, on Wikipedia)

The Beyonwiz EPG is in DVB EIT format, and allows only 16 bits (strictly a subrange of that, from 0x0001-0xfff7) for event ids. IceTV uses much larger event ids, 11 decimal digits. To reduce the range of the IceTV event ids, the Beyonwiz IceTV plugin reduces the event id range with:

eit_id = icetv_id % 0xfff7 + 1

With a 16-bit hash used to reduce the IceTV event ids to EIT event id size, and about 200 events/channel in the EPG (the problem only occurs when the same short event id is used for two different programs on the same channel), there's about a 25% probability that at least two different events will have the same hash, if the hashes are uniformly distributed.

When a collision occurs, the event already in the EPG with that EIT event id is removed, and the event that collided is added to the EPG. The EPG allows lookup of an event by its EIT event id, so multiple events with the same EIT event id can't co-exist in the EPG.

The IceTV event ids are not uniformly distributed, they tend to run in sequences, and the simple modulo hash used in the Beyonwiz IceTV plugin tends to preserve those sequences (e.g, a modulo 10 hash of 25, 26, 27 will be 5, 6, 7; even a prime modulo of 11 will preserve the run - 3, 4, 5). That means that the collisions tend to cluster: if one collision occurs in a channel, there's a fairly high probability that a run of several collisions will occur, and that removes a block of entries from the EPG on the Beyonwiz side, even though all the data has been correctly sent and received. However, there seems to be about the same overall probability that collisions occur as in the uniform distribution case.

I have experimented with re-hashing the IceTV event id to remove runs (e.g. by using the IceTV event id's MD5 hash) before reducing it by the modulo hash. That stops blocks of missing entries in the EPG from happening, but it doesn't significantly change the total number of collisions and missing entries in the EPG. They're just scattered over more channels and are less obtrusive.

The problem can be fixed by avoiding assigning colliding hashes. That can be done either on the IceTV server side by avoiding assigning ids that hash to the same Beyonwiz hash as some other id in the current EPG, or on the Beyonwiz side by detecting and re-hashing collisions.

Replication steps

The problem can normally only be seen by manually checking the IceTV EPG on the Beyonwiz looking for missing shows. There are no messages in the debug logs that correspond to this problem. If EPG_DEBUG is enabled in lib/dvb/epgcache.cpp, then the log can be checked for "[EPGC] removing event" messages on events that should not be removed.

I have also checked the problem against IceTV EPG dumps provided to me by Daniel Hall at IceTV using a Python script to find and report on event id hash collisions.

I can attach the data and script if anyone wishes to double-check.

Comments (4)