Overhead Characteristics

Table 1: Processing overhead of the Whisper operations on a 1.5 Ghz Pentium IV with 512 MB RAM.

Operation	512-bit	1024-bit	2048-bit
update_signature	0.18 msec	0.45 msec	1.42 msec
verify_signatures	0.25 msec	0.6 msec	1.94 msec
generate_signature	0.4 sec	8.0 sec	68 sec

Overhead of Whisper: One of the important requirements of any cryptography based solution is low complexity. We performed benchmarks to determine the processing overhead of the Whisper operations. Table 1 summarizes the average time required to perform the whisper operations for $3$ different key sizes: $512-$ bit, $1024-$bit and $2048-$bit. As the key size increases, the RSA-based operations offer better security. Security experts recommend a minimum size of $1024$ bit keys for better long-term security.

We make two observations about the overhead characteristics. First, the processing overhead for all these key sizes are well within the limits of the maximum load observed at routers. For $2048$ bit keys, a node can process more than $42,000$ route advertisements within $1$ minute. In comparison, the maximum number of route advertisements observed at a Sprint router is $9300$ updates every minute [9]. For $1024$ bit keys, Whisper can update and verify over $100,000$ route advertisements per minute. Second, generate_signature() is an expensive operation and can consume more than $1$ sec per operation. However, this operation is performed only once over many days.

Overhead of Listen: By analyzing route updates for over $17$ days in Routeviews [8], we observed that $99\%$ of the routes in a routing table are stable for at least $1$ hour. Based on data from a tier-1 ISP, we find that a router typically observes a maximum of $20000$ active prefixes over a period of $1$ hour i.e., only $20000$ prefixes observe any traffic. If the probing mechanism uses a statistical sample of $10$ flows per prefix, the overhead of probing at the router is negligible. Essentially, the router needs to process $200000$ flows in $3600$ sec which translates to monitoring under $60$ flows every second (equivalent to $O(60)$ routing lookups). Even if the number of active prefixes scales by a factor of $10$, current router implementations can easily implement the passive probing aspect of Listen.

Active dropping and retransmission checks are applied only in the IP slow path and are invoked only when a prefix observes a combination of both incomplete and complete connections. To minimize the additional overhead of these operations, we restrict these checks to a few prefixes.