グローバルおよびローカルに一意の10文字のID

c c++ linux sip x86-64
グローバルおよびローカルに一意の10文字のID

10文字の一意のIDを生成する必要があります(SIP / VOIPの人々は、P-Charging-Vectorヘッダーのparam icid-valueであることを知る必要があります)。 各文字は、26個のASCII文字(大文字と小文字が区別されます)、10個のASCII数字のいずれか、またはハイフンマイナスでなければなりません。

「グローバルに一意(idを生成するマシンの外部)」であり、十分に「ローカルに一意(idを生成するマシンの内部)」でなければならず、すべて10文字にパックする必要があります!

これが私の考えです。 私は最初に「MUST」をエンコードし、グローバルに一意のローカルIPアドレスをbase-63にエンコードします(エンコード後に1〜6文字を占める符号なしlong int)、そして可能な限り現在のタイムスタンプ(エンコードされたIPアドレスが最初に占めるスペースの量に応じて、エンコード後に9〜4文字を占めるtime_t / long long int)。

また、ループカウント ‘i’をタイムスタンプに追加して、関数が1秒間に複数回呼び出される場合に一意性を保持します。

これは、グローバルおよびローカルで一意になるのに十分ですか、または別のより良いアプローチがありますか?

ガウラフ

#include
#include
#include

//base-63 character set
static char set[]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-";

// b63() returns the next vacant location in char array x
int b63(long long longlong,char *x,int index){
    if(index > 9)
        return index+1;

    //printf("index=%d,longlong=%lld,longlong%63=%lld\n",index,longlong,longlong%63);
    if(longlong < 63){
        x[index] = set[longlong];
        return index+1;
    }

    x[index] = set[longlong%63];
    return b63(longlong/63,x,index+1);
}

int main(){
    char x[11],y[11] = {0}; /* '\0' is taken care of here */

    //let's generate 10 million ids
    for(int i=0; i<10000000; i++){

        /*  add i to timestamp to take care of sub-second function calls,
            3770168404(is a sample ip address in n/w byte order) =                84.52.184.224 */
        b63((long long)time(NULL)+i,x,b63((long long)3770168404,x,0));

        // reverse the char array to get proper base-63 output
        for(int j=0,k=9; j<10; j++,k--)
            y[j] = x[k];

        printf("%s\n",y);
    }

    return 0;
}

  0  0


ベストアンサー

_
「グローバルに一意(idを生成するマシンの外部)」であり、十分に「ローカルに一意(idを生成するマシンの内部)」でなければならず、すべて10文字にパックする必要があります!
_

IDを生成するすべてのソフトウェアを管理していますか? あなたはIDを使い果たしていますか? そうでなければ…​

SIPについては何も知りませんが、仕様について誤解している必要があります(または仕様が間違っている必要があります)。 別の開発者が、作成したアルゴリズムとは異なるアルゴリズムを使用してIDを構築しようとすると、そのIDとの衝突が発生します。つまり、そのシステムでグローバルに一意であることがわかります。

SIPドキュメントに戻って、これらのIDを生成するためのアルゴリズムの付録があるかどうかを確認します。 または、これらのIDを生成するためのSIPアルゴリズムが何であるかを答えるよりも賢いSOユーザーかもしれません。

5


128ビットのGUIDの生成について説明しているRFC 4122を真剣に検討します。 いくつかの異なる生成アルゴリズムがあり、そのうちのいくつかは適合するかもしれません(MACアドレスベースのものが思い浮かびます)。 これは、63 ^ 10 = 9.8 * 10 ^ 17と比較して、2 ^ 128 = 3.4 * 10 ^ 38よりも大きい数値空間であるため、一意性についていくつかの妥協が必要になる場合があります。 IDが生成される頻度などの要因を考慮してください。

ただし、RFCでは、IDのブロックを事前に割り当てることで、多数の一意の値を効率的に生成する機能など、いくつかの実用的な問題を考慮しています。

2


分散IDテーブルを作成することはできませんか?

1


NATされたLAN上のマシンはしばしば狭い範囲のIPを持ち、32ビット値のすべてが有効とは限りません(マルチキャストなど)。 特に粒度が大きい場合(秒など)、マシンは同じタイムスタンプを取得することもあります。年は同じになることが非常に多いため、最も低い「一意性」が得られることに留意してください。

さまざまな値を取得し、暗号化ハッシュでハッシュし、使用を許可されている文字に変換して、10文字に切り捨てることができます。

ただし、60ビット未満の値を扱っています。衝突の影響について慎重に考える必要があります。 問題に間違った方法でアプローチしている可能性があります…​

1


さて、これが悪い考えだと思うという事実を脇に置き、あなたの問題の解決に集中するなら、私は次のようにします:

idの範囲は10 ^ 63で、これは約60ビットに相当します。 「グローバルに」および「ローカルに」一意の両方にする必要があります。 最初のNビットをグローバルに一意に生成し、残りをローカルに一意に生成します。 2つの連結には、探しているプロパティがあります。

まず、グローバルな一意性:IPは動作しません。特にローカルIPはほとんどエントロピーを保持しません。 MACアドレスを使用します。これらはグローバルに一意であるために作成されました。 256 ^ 6の範囲をカバーするため、最大6 * 8 = 48ビットを使用します。

さて、ローカルで一意の場合:プロセスIDを使用しないのはなぜですか? 一意性はプロセスごとであると仮定していますが、そうでない場合は、何か他のものを考える必要があります。 Linuxでは、プロセスIDは32ビットです。 nitpickしたい場合、ほとんどのマシンで0になっているように、2つの最上位バイトはおそらくほとんどエントロピーを保持していません。 あなたが何をしているのかわかっているなら、それらを捨ててください。

したがって、最大70ビットを使用して適切な(ただし防弾ではない)グローバルおよびローカルに一意のIDを生成するため、問題が発生することがわかります(とにかく私の手法を使用して)。 また、念のために乱数(少なくとも8ビット長)を入力することをお勧めしますので、それは間違いなく適合しません。 ですから、私があなたなら、生成された〜78ビットをSHA1にハッシュし(たとえば)、結果のハッシュの最初の60ビットをID形式に変換します。 これを行うには、63文字の範囲から選択できることに注意してください。つまり、6ビットのほぼ全範囲になります。 したがって、ハッシュを6ビットに分割し、最初の10個を使用して、63文字の範囲からIDの10文字を選択します。 明らかに、6ビットの範囲は64の可能な値です(63だけが必要です)。したがって、6ビットピースが63に等しい場合、62にフロアするか、63を法として0を選択します。 分布にわずかな偏りがありますが、それほど悪くはありません。

そのため、適切なグローバルおよびローカルの疑似一意IDを取得する必要があります。

最後のいくつかのポイント:http://en.wikipedia.org/wiki/Birthday_paradox[Birthday_paradox]によると、1億4200万個のIDを生成した後、衝突の確率が1%、99%の確率で生成されます30億のIDを生成します。 したがって、商業的に大きな成功を収め、数百万のIDが生成される場合、より大きなIDを取得してください。

最後に、私はあなたの問題に「悪いよりも良い」解決策を提供したと思いますが、この問題を間違った方法で攻撃していると思わずにはいられません。 したがって、「防弾」となる他の方法がない場合はこれを使用してください(集中IDプロバイダー、はるかに長いID …​ ).

*編集:*質問を読み直しますが、この関数を1秒間に何回も呼び出す可能性があります。 これはある種のアプリケーションIDとして機能し、アプリケーションの開始時に一度生成され、終了するまで変更されないと想定していました。 そうではないので、間違いなく乱数を追加する必要があります。また、大量のIDを生成する場合は、少なくとも32ビットの数にしてください。 そして、上記にリンクした誕生日のパラドックスを読んで、もう一度読んでください。 そして、例えば現在のタイムスタンプのusec値のような非常にエントロピーの値に番号ジェネレーターをシードします。 または、/ dev / urandomからランダムな値を取得することもできます。 非常に正直なところ、あなたの努力に対する私の見解は、60ビットではおそらく十分ではないということです…​

1


うーん、システムクロックの使用は弱点かもしれません…​ 誰かが時計を戻すとどうなりますか? 同じIDを再生成する場合があります。 ただし、時計を使用する場合は、time()ではなくgettimeofday()を呼び出すことができます。少なくともそのようにすると、1秒よりも高い解像度が得られます。

0


@ダグ・T いいえ、IDを生成するすべてのソフトウェアを制御しているわけではありません。 標準化されたアルゴリズムがなければ衝突する可能性があることに同意し、適切なメーリングリストでこの問題を提起しました。

@Florianあなたからの手がかりは返信です。 idのスペース固有のコンポーネントとして、32ビットの乱数に/ dev / urandom PRNGを使用することにしました。 すべてのマシンには独自のノイズシグネチャがあり、一瞬のうちに安全にグローバルに一意であると想定できると思います。 以前に使用した時間固有のコンポーネントは同じままです。

これらの一意のIDは、コール処理中に特定のコールの課金情報を個別に生成したさまざまなネットワーク機能から収集されたすべての請求情報を照合するために生成されます。

以下が更新されたコードです。

ガウラフ

 #include
 #include
 #include

 //base-63 character set
 static char set[]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-";

 // b63() returns the next vacant location in char array x
 int b63(long long longlong, char *x, int index){
     if(index > 9)
         return index+1;

     if(longlong < 63){
         x[index] = set[longlong];
         return index+1;
     }

     x[index] = set[longlong%63];
     return b63(longlong/63, x, index+1);
 }

 int main(){
     unsigned int number;
     char x[11], y[11] = {0};

     FILE *urandom = fopen("/dev/urandom", "r");
     if(!urandom)
         return -1;

     //let's generate a 1 billion ids
     for(int i=0; i<1000000000; i++){

         fread(&number, 1, sizeof(number), urandom);

         // add i to timestamp to take care of sub-second function calls,
         b63((long long)time(NULL)+i, x, b63((long long)number, x, 0));

         // reverse the char array to get proper base-63 output
         for(int j=0, k=9; j<10; j++, k--)
             y[j] = x[k];

         printf("%s\n", y);
     }

     if(urandom)
     fclose(urandom);

     return 0;
 }

0


タイトルとURLをコピーしました