1つが壊れ、もう1つが失われました：データを送信するタスク

こんにちは、Habr！



ここからの写真



脳のトレーニングとして次のタスクを提案します。

2台の車が互いに通信します。 彼らはお互いにデジタルデータを送信します。当然ゼロと1です。 それらの間のチャネルだけはあまりありません。ビットは定期的に歪められ、その後完全に消えます。 平均で20ビットのチャネルが1ビットを中断し、もう1チャネルが損失すると仮定します。 そして現在、このデータを最適に転送するアルゴリズムを作成しています。

ネットワークペイロードのオーバーヘッドと、送信マシンおよび受信マシンの動作時間の間で妥協点を見つける必要があります。 そして、歪んだビットがよく知られているまたは独自の補正アルゴリズムを使用して修復できる場合、受信マシンに到達していない失われたビットについては、再送信を編成する必要があります。 しかし、受信マシンからの再送信のリクエストも失われる可能性があります...チャレンジを感じますか？



IEEEや関連組織の真面目な人たちが長い間すべてを思いついてきたと言うでしょう。あなたは正しいでしょう。 しかし、いつlulzのためにあなたが再発明するのを止めたのですか？ そして、しばらくの間、信頼性の高いシンプルなソケットの快適ゾーンから抜け出しますか？ さらに、これをJavaScriptで、ブラウザで、サードパーティライブラリなしで行います。1つの画面に収まることが望ましいです。



こっち



JavaScriptに対する多くの人の偏見を理解していますが、ブラウザに埋め込むことができるのは5分であり、編集と実行が可能になりました。 擬似コードで書いているかのような単純な基本構文。



すべてのコードはローカルで実行されます。 CodeMirrorはコードエディターに接続されています。 送信（送信者\ソース）および受信（受信者\宛先）マシンで定期的に呼び出される2つの関数の内容を記述します。



this



コンテキストは自由に使用できますが、すでに5つのメソッドがあります。

 var runs = this.counter();
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

基本関数が呼び出された回数のカウンター。 たとえば、タイムアウトをカウントするために、時間内にナビゲートするのに役立ちます。

 var frame = this.getPayload(n);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

トランスミッション機で利用可能。 ペイロードの次のn



ビットを読み取り、返します。

 this.write(frame);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ビットの配列であるframe



を別のマシンに渡します。 伝送チャネルを通過すると、メッセージが歪む可能性があります。

 var frame = this.read(n);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

着信ネットワークバッファから最大n



ビットを読み取ります。 何もなければ、空の配列を返します。

 this.acceptPayload(frame);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ホストマシンで使用可能。 結果の配列にframe



を入れます。



main関数がtrue



返すtrue



、将来再び呼び出されることを望みます。 それ以外の場合、マシンは実行を完了します。 受信マシンでは、受信データの整合性チェックが呼び出され、オーバーヘッドも計算されます。



ソースコードの例をいくつか追加しました。

• チュートリアルは、送信機と受信機の機能のもう少し詳細な説明です。
• 修正なし -送信データの整合性を監視しない最も単純なアルゴリズム。 オーバーヘッドはありませんが、整合性は不十分です。
• Naive 900％Overhead-名前から明らかだと思います。 ヘルメットを1ビットずつゆっくりと複製し、10回複製しました。 それは多かれ少なかれ安定して動作します（ただし、整合性は時々壊れます）が、ネットワーク負荷のオーバーヘッドは900％です。
• +リクエストの再送 -haldaganによって提案されたシンプルなオプションですが 、100％の整合性は提供されませんが、オーバーヘッドを〜550 ％に減らし、 再送リクエストでエラーを修正しようとします。

この記事の最初のアイデアと最後のポイント（最初のバージョン）の間、これまでに12時間未満しか経過していません。 書いて、できるだけ早く訂正します。



UPD：帽子の解析に間に合うように到着した私のバージョンは次のとおりです。

• 著者の提案は 、エラー検出コードを含む短いメッセージを送信し、リクエストに応じて再販します。 致命的な破損データ10 ⁷あたり約3ビット