Microsoft Technology Licensing, LLC

Microsfot Corporation

Micdrosoft Corporation

Ofer Bar

Yoram Bernet

John R Douceur

Eric Lynn Eilebrecht

Tsung-Yuan Charles Tai

Rajendra S Yavatkar

Carol Ann Bell

A traffic control application programming interface for abstracting the use of traffic control components to client applications to provide quality of service. The traffic control interface accepts input from a client application and based on that input, communicates with the operating system to control kernel level traffic control components. The client can register with the traffic control interface, and it can open and close interfaces, add, modify, and delete flows on those interfaces, and attach or delete filters on the flows. The client can also obtain data on any currently active interface, flow, or filter. The traffic control interface will send the appropriate message to the operating system, directing that the necessary tasks be performed by either a packet scheduler or a packet classifier. Those kernel level components then return through the operating system the results of the operations requested, and that return data will be passed back to the client application.

Method and system of a traffic control application programming interface for abstracting the use of kernel-level traffic control components

Method and system of an application program interface for abstracting network traffic control components to application programs

A method and computer program product for scheduling network communication packets in a multimedia environment where different packet streams have reservations of network bandwidth to form packet flows. The present invention divides the packet scheduling function into distinct components that may be implemented as separate drivers in a layered driver environment as exists, for example, in the Microsoft Windows NT operating system. One component is called a conformer and will generate and assign to each packet in the packet flow at least one conformance time that signifies the earliest a packet may be sent and still conform to the network resource requirements associated with the flow. Many different conformance algorithms can be supported so that the best algorithm is used for a particular packet flow and the service requirements that it represents. Should it be necessary to actually hold a packet until the conformance time is met, a shaper component is used to delay the packets. Finally, a sequencer component will send packets out as fast as possible over the network interface card. Each flow of packets processed by the sequencer component has at least two priorities, one for when the packets are conforming and one for when the packets are non-conforming. The sequencer component maintains priority lists of packet flow queues and will service the highest priority queue list followed by each successive priority list until no packets remain for transmission or the network interface card is unable to handle more packets. Each priority list will have a queue discipline associated therewith that will determine in what order the packets are taken off of the respective flow queues.

Method and computer program product for scheduling network communication packets originating from different flows having unique service requirements

A method and computer program product for classifying data being processed by drivers included in a stack. The computer program product is a centralized packet classifier that receives classification requests from drivers or other clients according to a defined interface. This reduces the cost for producing a driver since less code is required initially at development time as well as a corresponding reduction in maintenance costs. The present invention groups drivers or other clients that utilize a certain body of classification information into classification families. Further, reference patterns used to make classifications are stored in separate databases depending on whether they are specific or general. There exists a single specific pattern database for all specific reference patterns regardless of classification family having a constant search time and a general pattern database for each general reference pattern for each classification family defined to the system whose search time may vary according to the amount of information contained therein. When servicing a classification request, the packet classifier will first search the specific pattern database followed by a search in the appropriate general pattern database if necessary.

Classifying data packets processed by drivers included in a stack

The present invention is embodied in a system and method for generating and validating reference handles for consumers requiring access to resources in a multi-threaded environment of a computer system. The system of the present invention includes a resource manager having a handle administrator, a plurality of consumers, and a plurality of resources. The handle administrator includes an assignment routine, a release routine, a dereference routine, and multi-threading sub-routines enabling operation of the present invention in multi-threaded environments. The assignment routine issues new handles, the release routine releases handles that are no longer required (thus rendering the handle invalid), the dereference routine dereferences handles into a pointer to a resource, which entails verifying that the handle is valid, and the multi-threading sub-routines enable safe invalidation of handles in multi-threaded environments and also ensure consistent use of pertinent values, such as array pointers and array sizes during operation of the expansion and contraction sub-routines.

Generation and validation of reference handles in a multithreading environment

The present invention is embodied in a system and method for generating and validating reference handles for consumers requiring access to resources in a computer system. The system of the present invention includes a resource manager having a handle administrator, a plurality of consumers, and a plurality of resources. The handle administrator includes an assignment routine, a release routine, and a dereference routine. The assignment routine issues new handles, the release routine releases handles that are no longer required (thus rendering the handle invalid), and the dereference routine dereferences handles into a pointer to a resource, which entails verifying that the handle is valid. Also included is an auxiliary sub-routine for managing used and unused records, an expansion sub-routine for efficiently expanding the handle database, a handle recycling sub-routine for recycling handles, a contraction sub-routine for efficiently contracting the handle database, a hysteresis sub-routine for probabilistically contracting the handle database, and a memory allocation failure sub-routine to improve functionality in the event of memory allocation failure.

System and method for recycling numerical values in a computer system

The present invention is embodied in a system and method for reducing the likelihood of the location conflicts in a system with a database of records having an initial size. A logical location of each record is dependent upon data contained in each record and the database size and wherein a change in the database size by a resizing factor creates a likelihood of a location conflict between two records. The present invention reduces the likelihood of the location conflict by maintaining a first list of unused records, wherein the first list contains unused records that, if used, would not have location conflicts with any record currently used and would not have location conflicts with any other records contained in the first list. Also, a second list of unused records is maintained, wherein the second list contains unused records that are not contained in the first list. An unused record from the first list is selected if the first list is not empty when a datum is added to the database and an unused record from the second list is selected only if the first list is empty when a datum is added to the database.

System and method for reducing location conflicts in a database

Generation and validation of reference handles

Hysteresis system and method for achieving a mean constant cost per

A technique, specifically apparatus and accompanying methods, which utilizes a trie-indexed hierarchy forest ('rhizome') that accommodates wildcards for retrieving, given a specific input key, a pattern stored in the forest that is identical to or subsumes the key. The rhizome contains a binary search trie and a hierarchy forest. The search trie provides an indexed path to each unique, most specific, pattern stored in a lowest level of the hierarchy forest and also possibly to increasingly general patterns at higher levels in the pattern hierarchy. The hierarchy forest organizes the patterns into nodal hierarchies of strictly increasing generality. For use as a packet classifier, the rhizome stores wildcard-based packet classification patterns at separate corresponding pattern nodes, along with, corresponding 'reference' fields associated therewith. Operationally, as each different queue is established or removed, a corresponding classification pattern is either inserted into or removed from the rhizome. A search key is formed for each packet, typically by concatenating classification fields, e.g. source and destination addresses and source and destination port designations, appearing in a header of the packet. The search key is then applied to the rhizome to determine whether that key exists therein, by virtue of either matching an identical classification pattern or being completely subsumed within a more general pattern stored therein. When such a classification is found, the classifier returns the contents of the associated reference field, which for scheduling, is a designation of a transmission queue to which the packet is to be directed.

Technique for efficiently classifying packets using a trie-indexed

A technique, specifically apparatus and accompanying methods, which utilizes a trie-indexed hierarchy forest ('rhizome') that accommodates wildcards for retrieving, given a specific input key, a pattern stored in the forest that is identical to or subsumes the key. The rhizome contains a binary search trie and a hierarchy forest. The search trie provides an indexed path to each unique, most specific, pattern stored in a lowest level of the hierarchy forest and also possibly to increasingly general patterns at higher levels in the pattern hierarchy. The hierarchy forest organizes the patterns into nodal hierarchies of strictly increasing generality. For use as a packet classifier, the rhizome stores wildcard-based packet classification patterns at separate corresponding pattern nodes, along with, corresponding 'reference' fields associated therewith. Operationally, as each different queue is established or removed, a corresponding classification pattern is either inserted into or removed from the rhizome. A search key is formed for each packet, typically by concatenating classification fields, e.g., source and destination addresses and source and destination port designations, appearing in a header of the packet. The search key is then applied to the rhizome to determine whether that key exists therein, by virtue of either matching an identical classification pattern or being completely subsumed within a more general pattern stored therein. When such a classification is found, the classifier returns the contents of the associated reference field, which for scheduling, is a designation of a transmission queue to which the packet is to be directed.

Apparatus and accompanying methods, using a trie-indexed hierarchy

A method and computer program product for classifying network communication packets being processed in a network stack. The computer program product is a centralized packet classifier that receives classification requests from drivers or other clients according to a defined interface. This reduces the cost for producing a driver since less code is required initially at development time as well as a corresponding reduction in maintenance costs. The present invention groups drivers or other clients that utilize a certain body of classification information into classification families. Further, reference patterns used to make classifications are stored in separate databases depending on whether they are specific or general. There exists a single specific pattern database for all specific reference patterns regardless of classification family having a constant search time and a general pattern database for each general reference pattern for each classification family defined to the system whose search time may vary according to the amount of information contained therein. When servicing a classification request, the packet classifier will first search the specific pattern database followed by a search in the appropriate general pattern database if necessary.

Growing community of inventors

Newcastle, WA, United States of America

Ofer Bar