Je développe un algorithme pour réorganiser des paquets dans une transmission. Chaque paquet a un numéro de séquence associé dans [0, 256). Le premier numéro de séquence de la paquet peut prendre l'une de ces valeurs, après quoi le paquet suivant prend la valeur suivante et le prochain paquet la valeur après cela, etc. (rouler après 255).
Les numéros de séquence des paquets, dans le bon ordre, apparaîtraient comme suit, où "n" est le numéro de séquence du premier paquet:
N, N + 1, N + 2, ..., 254, 255, 0, 1, 2, ..., 254, 255, 0, 1, 2, ..., 254, 255, 0 , 1, ...
Chaque paquet reçoit un horodatage lorsqu'il arrive à destination, et ils arrivent tous environ dans l'ordre. (Je n'ai pas de chiffre exacte, mais donnée une liste de paquets triés par horodatage d'arrivée, il est prudent de dire qu'un paquet ne sera jamais plus de cinq taches de sa position dans la liste indiquée par son numéro de séquence.)
Je pense que je ne peux pas avoir été la première personne à faire face à un problème comme celui-ci, compte tenu de la prévalence des télécommunications et de son importance historique pour le développement de l'informatique. Ma question, alors:
existe un algorithme bien connu pour réorganiser une séquence approximativement ordonnée, telle que celle décrite ci-dessus, étant donné une clé changeante cyclique?
y a-t-il une variante de cet algorithme tolérant de gros morceaux d'articles manquants? supposons que ces morceaux puissent être de n'importe quelle longueur. Je suis spécifiquement inquiet des morceaux de 256 objets manquants ou plus. J'ai quelques idées d'algorithmes pour la première, mais pas pour la seconde. Avant d'investir les heures d'homme pour vérifier que mes algorithmes sont corrects, cependant, je voulais m'assurer que quelqu'un chez Bell Labs (ou ailleurs ailleurs) ne l'avait pas déjà fait il y a trente ans.
3 Réponses :
Utilisez une file d'attente prioritaire.
Après chaque réception de chaque paquet:
pour la deuxième question:
Pour clarifier: 1) Que dois-je utiliser comme clé dans la file d'attente prioritaire? 2) Comment saurai-je que le paquet est censé venir en premier?
a) Vous pouvez utiliser le numéro de séquence, auquel cas vous devez effectuer la comparaison entre une mode circulaire ... (255 <0, vous pouvez utiliser une règle simple comme tout ce qui est supérieur à 240 est inférieur à 10). . b) Vous pouvez utiliser un séquençage interne, qui augmente toujours ... (0..255 Maps à 0..255, la prochaine exécution de 256..511, etc.). Étant donné que les paquets sont au plus 5 endroits loin de leur position d'origine, vous savez toujours mapper.
problème intéressant!
Ma solution serait trier les paquets en fonction de l'heure d'arrivée et trier localement une fenêtre d'éléments (disons 10) circulairement en fonction de leur numéro de paquet. Vous pouvez affiner cela à bien des égards. Si la différence entre deux nombres de paquets consécutifs (arrangés en fonction de l'heure d'arrivée) est supérieure à certains seuils, vous pourriez mettre une barrière entre eux (c'est-à-dire que vous ne pouvez pas trier les barrières). De plus, si la différence de temps entre les paquets (arrangée en fonction de l'heure d'arrivée) est supérieure à un seuil que vous pourriez vouloir mettre une barrière (cela devrait probablement s'occuper du problème 2).
Je ne sais pas si cette solution est réellement utilisée n'importe où, mais voici ce que j'essaierais (en supposant qu'aucun paquets manquants, un "dépouteuse" maximum de cinq positions et un nombre maximum de séquence de 255):
127,130,128,129
Comment feriez-vous une disposition si nous n'avions pas la garantie que le numéro de séquence du premier paquet ( N dans votre exemple, je crois) est 0? Dans le pire des cas: que si le paquet 255 a été envoyé en premier, mais le paquet 0 et 1 arrivent en premier?
Hmm, pas sûr. En fait, je ne pense pas que ce problème soit si courant, de mon expérience. Habituellement, les numéros de séquence sont beaucoup plus importants pour tenir compte de cela. Le seul endroit où j'ai jamais vu quelque chose de plus bas que celui-ci dans un numéro de séquence sont concatérés SMS GSM, qui vont jusqu'à 255 Afaik. Cependant, il s'agit de 256 SMS par expéditeur avant d'emballer et même s'il existe un codage différent qui permet des numéros de séquence plus importants dans les SMS concaténés. Certains protocoles ont même des identifiants uniques globaux. Quelle était la raison pour choisir une telle gamme?
Pour faire une longue histoire courte, les numéros de séquence n'ont jamais été destinés à recréer une transmission. Les données ont été transmises à l'origine sur un câble série courte. Les numéros de séquence étaient principalement un outil de débogage et une vérification de la santé mentale. Ensuite, toutes les exigences soudaines du projet ont changé, mais cette fonctionnalité est congelée depuis longtemps. Je pense que je pourrais être capable de le faire si j'examine les jeux de données particuliers et que je peux caractériser le taux de transmission moyen (je soupçonne qu'il est proche de <1 par seconde).