Техника для отслеживания и обнаружения недостающих данных в серии (например, данные журнала безопасности)

У меня есть поток данных, который отправляет мне данные с постоянно увеличивающимся индексом (n++). Возможно, что некоторые из этих данных будут отправлены не по порядку, потеряны или иным образом потребуются повторная передача.

пример

  1. Предположим, у меня есть файл журнала безопасности, который отслеживается моим приложением. Плохой парень может подавить или предотвратить передачу нескольких записей. Я хочу быть предупрежденным об этом факте.

  2. Также предположим, что эти данные могут быть отправлены в регистратор не в порядке.

Кажется, эта логика везде, где я не хочу изобретать велосипед и делать что-то менее эффективное.

Вопрос

Как мне реализовать (или какая эталонная реализация существует), которая позволяет мне отслеживать данные, полученные не по порядку, и может содержать отсутствующие данные в последовательности?

(Также приветствуется ваша помощь в пометке этого вопроса)

Источник

3 ответа

Решение

Хорошо, я сделал это, используя связанный список. Для этого где-то должна быть проведена предварительная работа... в любом случае, это оптимизировано для входных рядов, которые более или менее растут по своей природе.

Дайте мне знать, если увидите какие-либо ошибки или улучшения, которые я могу сделать

    public class ContiguousDataValue
    {
        public int UpperInt { get; set; }
        public int LowerInt { get; set; }

        public override string ToString()
        {
            return "Upper" + UpperInt + " Lower" + LowerInt; 
        }
    }


public class ContiguousData 
{
    LinkedList<ContiguousDataValue> ranges = new LinkedList<ContiguousDataValue>();

    public void AddValue(int val)
    {
        for (LinkedListNode<ContiguousDataValue> range = ranges.Last; range != null; range = range.Previous)
        {
            if (val > range.Value.UpperInt)
            {
                // increment current node if applicable 
                if (val == range.Value.UpperInt + 1)
                    range.Value.UpperInt = val;
                else
                    ranges.AddAfter(range, new ContiguousDataValue() { UpperInt = val, LowerInt = val });
                return;
            }
            else if (val < range.Value.LowerInt)
            {
                if (val == range.Value.LowerInt - 1)
                {
                    range.Value.LowerInt = val;
                    return;
                }
                else
                {
                    continue;
                }
            }
        }
        // Anything that reaches this line is either a very new low value, or the first entry
        ranges.AddLast(new ContiguousDataValue() { UpperInt = val, LowerInt = val });
    }
 }
Источник

Вы упомянули каноническую реализацию в вашем OQ: TCP. Таким образом, отправка данных через TCP имеет несколько желательных последствий,

  • всякий раз, когда (ifever) данные поступают не по порядку, вы можете с уверенностью предположить, что ваша отправка или процесс получения ведут себя неправильно.
  • Всякий раз, когда в последовательности отсутствуют данные, вы можете предположить, что
  • То же самое относится и к подтверждению, так что ваш процесс отправки всегда в порядке.

Я настоятельно советую просто использовать TCP в качестве транспорта и (если это не осуществимо напрямую) просто инкапсулировать дейтаграммы TCP в другой сетевой поток.

Вкратце: сделайте каноническую реализацию вашей реализацией.

Источник

Прежде всего, если у вас есть потенциальное состояние гонки, вы должны это исправить.

TCP преодолевает проблему неупорядоченных данных путем ожидания. Если пакет 6 прибывает после пакета 4, TCP будет ждать, пока пакет 5 не прибудет. Если пакет 5 не приходит в течение определенного периода времени, TCP запросит повторную передачу пакета 5, что приведет к повторной отправке пакета 5.

(Примечание: я знаю, что TCP/IP считает байты, а не пакеты, здесь это не имеет значения)

Если вы можете попросить ваше "тупое встроенное устройство" повторить передачу, вы можете использовать ту же технику. Бьюсь об заклад, вы не можете сделать это, поэтому вам придется прибегнуть к другому механизму. Это может быть похоже на то, что делает TCP. Вам просто нужно решить, как долго вы будете ждать, пока не решите, что запись отсутствует.

Источник
Другие вопросы по тегам