InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Using Color Codes to improve validations in highly random number space

IP.com Disclosure Number: IPCOM000199922D
Publication Date: 2010-Sep-21
Document File: 7 page(s) / 260K

Publishing Venue

The IP.com Prior Art Database


Typically companies constantly face the need to separate the wheat from the chaff i.e. they need to cleanly separate the usable ids from the unwanted ones. The unwanted ones are typically some ids which are reserved for internal use or ids which had been counterfeited earlier in history(hence they can't be re-used due to legal constraints). One important consequence of this is the need for quick validation. I've discussed at length about the various approaches towards validation and sort-of "zeroed in" on the optimistic approach towards the end of the draft. Besides this, companies are constantly trying to ramp up their security capabilities by enabling cryptographic signatures to their id generation process. By obfuscating the id sequence, different items get mixed up (during packaging at case/pallet/container levels) and hence a counterfeit operation can't harm the entire batch of "similar" items. Without this obfuscation, if the items are repeatedly replaced by a counterfeiter, the losses due to counterfeiting can be phenomenal. Of course, this obfuscation technology indeed adds to the cost and hence must be used for costly/life-saving drugs or mission-critical appliances. Thus, another consequence is the need for randomizing ids as a measure towards anti-counterfeiting. In gist, this draft aims to solve the problem of validating ids quickly within a highly randomized number space. Since the number space is random, it in itself adds new challenges to the process of validation.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 33% of the total text.

Page 1 of 7

Using Color Codes to improve validations in highly random number space

Here I describe an approach towards blacklisting numbers in a highly randomized number space.

Blacklist Application(Quick background info)

Blacklists are "unwanted ids" or "reserved ids" which are
debarred from commercial use. Therefore, any number allocation
application if configured with set of blacklisted ids should NOT
ever emit those blacklisted numbers while allocating requests.


User specifies a range of numbers to be blacklisted. Our goal is
to first perform validation and then persist this blacklist if it
passes through the validation. In addition, we can update our
persistent store by shifting numbers around to reflect the

Terminologies Used:


            Space consisting of all possible numbers
supported by the number allocation engine. This space can be
sequential or random.
2. Confirmed Numbers: These refer to numbers that have been
already allocated.


Number Space:

                These numbers are available for

Available Numbers:

                         T hose numbers that are
restricted from use. Think of it as "Reserved Sets" whose
values are NOT to be strictly used. Like "all bits being 1"
is reserved for broadcasting purposes in networks.

To understand the validation of blacklists, look at the figure

Already Blacklisted Numbers:

Rules for a blacklist to pass validation:



[This page contains 1 picture or other non-text object]

Page 2 of 7

1. If the blacklist hits any of the RED parts, it's an invalid

2. Else it passes the validation.(i.e. can hit blacks and
greens )


persistent store is used for reliability as well as to scale upto

millions of ids.

Complexities involved: The number space is Random!

The figure above is actually a bit misleading to the "human eye".
It gives you an illusion of contiguous REDs ,BLACKs and GREENs .
But since the underlying number space is random, so let's take a
second look at it.

Now we need to check if the blacklist hits the RED parts. This
means to check if each of the numbers listed in the REDs (see
figure above) falls in that blacklist range or not. This check is
costly and time consuming if the REDs are more frequent and/or
spawn a large area in the random number space. Also, if these
REDs are internally stored as blobs in a persistent store,there's
storage latency in fetching and updating the random ids( Note:
use of a persistent store is encouraged here for more reliability
and scalability).

Blacklist post-validation : Perform Defrag

This step is mainly applicable for random number space. Assume
our "valid" blacklist (represented by blue lines) hits few of the
greens in the figure below. Semantically the valid blacklist
range hits some of the available numbers at different points in
the number space(since it's a random number space! ).


Assumptions and Coloring Scheme Use

REDs : Confirmed ids
GREENs :All available, ready for allocation ids
BLACKs: Forbidden ids.

Note: These may in turn refer to a suitable row representing a