# US 2010/0166007 A1 · Advanced Elastic Time Recovery Mechanism Using Wildcard Searches

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0166007 A1
- Document ID: US20100166007A1
- Status: Published application
- Kind: A1
- Application number: 12/346,369
- Filed: 2008-12-30
- Published: 2010-07-01
- Earliest claimed: 2008-12-30
- Inventors: Jeremy Horner
- Web page: https://patentgrep.com/patent/US20100166007A1

## CPC

- H04L 47/568: {Calendar queues or timing rings}
- H04L 47/50: Queue scheduling
- H04L 47/564: {Attaching a deadline to packets, e.g. earliest due date first}
- H04L 47/6245: {Modifications to standard FIFO or LIFO}
- H04L 67/62: Establishing a time schedule for servicing the requests
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A scheduler for a server includes a timestamp associative array for storing timestamps. The scheduler includes an advanced elastic time recovery mechanism having a processor in communication with the associative array which uses a wildcard search to find at least one timestamp in the associative array to schedule for service by the server in a single search, and to increment operational time by more than 1 in a given clock cycle. A method of using a scheduler for a server includes the steps of storing timestamps in a timestamp associative array. There is the step of using a wildcard search of an advanced elastic time recovery mechanism having a processor in communication with the associative array to find a timestamp in the associative array to schedule for service by the server in a single search. There is the step of incrementing operational time by more than 1 in a given clock cycle.

## Claims

### Claim 1

A scheduler for a server comprising:
a timestamp associative array for storing timestamps; and
an advanced elastic time recovery mechanism having a processor in communication with the associative array which uses a wildcard search to find at least one timestamp in the associative array to schedule for service by the server in a single search, and to increment operational time by more than 1 in a given clock cycle.

### Claim 2 (depends on 1)

The scheduler as described in claim 1 wherein the advanced elastic time recovery mechanism includes a state machine which monitors ideal time and operational time and calculates an elastic time difference (ETD) according to a formula:
ETD=ideal time−operational time.

### Claim 3 (depends on 2)

The scheduler as described in claim 2 wherein when the ETD equals zero, the state machine searches the timestamp associative array for a next eligible time by initiating a search using a timestamp search key equal to the operational time and a search mask equal to all 1's.

### Claim 4 (depends on 3)

The scheduler as described in claim 3 wherein when the ETD is greater than zero the wildcard search uses a wildcard search pattern composed of a search value and the search mask that the advanced elastic time recovery mechanism uses to cover not only the operational time, but also the greatest possible range of numbers between the operational time and the ideal time.

### Claim 5 (depends on 4)

The scheduler as described in claim 4 wherein the wildcard search determines the maximum number of timestamps that can be searched for, where the maximum number of timestamps is found by taking the ETD and rounding it down to a nearest power of 2.

### Claim 6 (depends on 5)

The scheduler as described in claim 5 wherein the wildcard search assumes that that the range of timestamps that is valid for searching does not include any timestamps that have already been searched for.

### Claim 7 (depends on 6)

The scheduler as described in claim 6 wherein the wildcard search determines that the operational time is divisible by 2, and in order to search the largest range of numbers, the wildcard search determines a largest divisor which equals 2 raised to the power of the number of least significant bits that are zero.

### Claim 8 (depends on 7)

The scheduler as described in claim 7 wherein the wildcard searches for the maximum number of time stamps if the operational time equals zero, or chooses a smallest value of the maximum number of timestamps and the largest power of 2 divisor of operational time when the operational time does not equal zero; where the result is defined as the number of timestamps.

### Claim 9 (depends on 8)

The scheduler as described in claim 8 wherein the search mask is formed by raising 2 to the power of (the number of timestamps -1), and doing a binary bitwise inversion of the search mask; the search mask along with a search key equal to the operational time is used to search for the desired range of timestamps.

### Claim 10

A method of using a scheduler for a server comprising the steps of:
storing timestamps in a timestamp associative array;
using a wildcard search of an advanced elastic time recovery mechanism having a processor in communication with the associative array to find at least one timestamp in the associative array to schedule for service by the server in a single search; and
incrementing operational time by more than 1 in a given clock cycle.

### Claim 11 (depends on 10)

The method as described in claim 10 including the steps of monitoring ideal time and operational time with a state machine of the advanced elastic time recovery mechanism; and calculating an elastic time difference (ETD) according to a formula:
ETD=ideal time−operational time.

### Claim 12 (depends on 11)

The method as described in claim 11 wherein when the ETD equals zero, there is the step of the state machine searching the timestamp associative array for a next eligible time by initiating a search using a timestamp search key equal to the operational time and a search mask equal to all 1s.

### Claim 13 (depends on 12)

The method as described in claim 12 wherein when the ETD is greater than zero there is the step of the wildcard search using a wildcard search pattern composed of a search value and the search mask that the advanced elastic time recovery mechanism uses to cover not only the operational time, but also the greatest possible range of numbers between the operational time and the ideal time.

### Claim 14 (depends on 13)

A method as described in claim 13 wherein the step of using the wildcard search includes the step of the wildcard search determining the maximum number of timestamps that can be searched for, where the maximum number of timestamps is found by taking the ETD and rounding it down to a nearest power of 2.

### Claim 15 (depends on 14)

The method as described in claim 14 wherein the step of using the wildcard search includes the step of the wildcard search assuming that that the range of timestamps that is valid for searching does not include any timestamps that have already been searched for.

### Claim 16 (depends on 15)

The method as described in claim 15 wherein the step of using the wildcard search includes the steps of the wildcard search determining that the operational time is divisible by 2, and in order to search the largest range of numbers, the wildcard search determining a largest divisor which equals 2 raised to the power of the number of least significant bits that are zero.

### Claim 17 (depends on 16)

The method as described in claim 16 wherein the step of using the wildcard search includes the step of using the wildcard search to search for the maximum number of time stamps if the operational time equals zero, or choosing a smallest value of the maximum number of timestamps and the largest power of 2 divisor of operational time when the operational time does not equal zero; where the result is defined as the number of timestamps.

### Claim 18 (depends on 17)

The method as described in claim 17 including the steps of forming the search mask by raising 2 to the power of (the number of timestamps -1), and doing it binary bitwise inversion of the search mask; the search mask along with a search key equal to the operational time is used to search for the desired range of timestamps.
