Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1996-04-25
2001-10-16
Courtenay, III, St. John (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
Reexamination Certificate
active
06304917
ABSTRACT:
TECHNICAL FIELD
This invention relates to systems of interconnected data or signal processing components and to methods for negotiating or selecting negotiable parameters to be used in interconnecting such components.
BACKGROUND OF THE INVENTION
There are many different types of systems in which signals or data are passed in a directed flow from source components (where the signals or data originate or enter the system), through transfer components (which may modify the signals or data), to sink components (where the signals or data terminate or exit the system). A multimedia computer is an example of such a system. In a multimedia computer, audio and video data might originate from a mass storage system, pass through decompression components, and be supplied to a speaker and a display device.
The invention described below will be used in a system for assembling software components or program modules that pass sampled audio and/or video data in a directed flow. She software components include source, transfer, and sink components. Each software component might be associated with one or more hardware devices and associated device driver programs. The invention could also be used in other contexts, such as in a computer program for simulating or modeling an interconnected system of source, transfer, and sink components.
FIG. 1
shows an example of an interconnected system of software components such as might be assembled in the context of this invention. Functionally, the system retrieves a compressed stream of sampled data representing a video segment from a mass storage device 12, decompresses the data, and displays it on a display device
13
. In addition to the two physical devices (mass storage device
12
and display device
13
), the system includes a source component
14
, a transfer component
15
, and a sink component
16
. Source component
14
is associated with a device driver
17
, in this case a hard disk driver, that handles details of communications with mass storage device
12
. Source component
14
retrieves data from hard disk
12
at appropriate intervals and prepares or formats the data for subsequent handling by transfer component
15
. Transfer component
15
is associated with decompression software
18
for decompressing data into a format suitable for handling by video display hardware. The decompressed data is received by sink component
16
, which is associated with a video display driver
19
for transferring the decompressed data to a video display card and associated display device
13
.
The component assembly system in which the invention is likely to be used allows a designer (or application program) to specify individual components, along with their individual propagation delays, and one or more direct connections between those components. The components and direct connections are specified one at a time, in an arbitrary sequence.
One issue that needs to be resolved, either by the components themselves or by the component assembly system on behalf of the components, is the format of the data as it is passed from each component to the next. It may be that each component supports a number of different format combinations. However, it will often be the case that the different components do not support the same sets of format combinations.
One way to negotiate format parameters is to allow each connected group of components to negotiate among themselves as they are being connected. In the example of
FIG. 1
, source component
14
and transfer component
15
would initially negotiate to select an optimum set of format parameters supported by both of the components. Once this connection was completed, transfer component
15
and sink component
16
would negotiate to select another set of format parameters supported by both of these components. In practice, each component would implement a negotiation interface which would be used to actively arbitrate with other components in determining a common communication format.
While this type of negotiation scheme might work in many situations, it does not always result in the optimum overall parameter selection. In this scheme, parameter decisions are made locally as individual components are connected. However, the most efficient parameter selection between two components may not be the most efficient selection when the entire path is considered. For instance, it might be in the example of
FIG. 1
that source component
14
and transfer component
15
both support a very efficient data format as well as a slightly less efficient data format, while sink component
16
supports only the less efficient format. Based on the scheme described above, the most efficient format would be chosen for the interconnection between source component
14
and transfer component
15
. However, this format would not be available for the interconnection between transfer component
15
and sink component
16
, so a format conversion would be required to convert the data to the less efficient format for transfer to sink component
16
. In this situation, it would have been more efficient to select the less efficient format for all interconnections, thus avoiding the processing penalty of the format conversion.
In practice, the problem of choosing appropriate or optimum format parameters can become far more complex than indicated by the example of FIG.
1
. For example, each component may have multiple input ports and multiple output ports, each of which might be connected to a different component. In addition, a negotiated parameter selection on one port of a component might impose restrictions on the format parameters available at other ports of the same component. Furthermore, there may be a hierarchy of parameter information, such that making one decision in a negotiation not only affects the choices that can be made for other parameters, but even determines which other parameters are relevant to the negotiation.
Even the task of designing negotiation interfaces is problematic. For instance, it is difficult to define interfaces that effectively support radically different classes of communication formats, since each class may require a substantially different form of negotiation. Furthermore, implementation of a negotiation interface requires a high degree of intelligence in each component, thus impeding the automation of the negotiation process. This requirement for component-level intelligence places a significant burden on the implementer of each component. One mechanism that can be employed to case this burden is the creation of generic ports, which are component ports that contain all of the basic logic for both data exchange and parameter negotiation, yet are not specific to any type of component. These generic ports can be instantiated by the component designer and modified as necessary to support the component's negotiation needs. However, since the negotiation interface that each port presents is so heavily dependent upon the classes of communication formats that are supported by the port's component, definition and implementation of generic ports is a difficult problem, and one that has no obvious solution.
It is apparent that the previously proposed methods of negotiating or selecting communication parameters for use among groups of interconnected components have a number of problems. The invention addresses these problems and allows parameters to be selected to provide the optimum overall performance.
SUMMARY OF THE INVENTION
The invention defers the selection of parameters until all relevant information is available. Parameter decisions are made only after all allowable values are known for each component port in light of the specified interconnections between components.
A parameter set is specified for each port. The parameter set indicates the allowable values for each parameter relevant to the communication formats supported by the component for the port. Each parameter set is expressed as a Boolean expression of constraints. A constraint is expressed as a parameter identifier and a value scope.
Douceur John R.
Glass Adam
Courtenay III St. John
Lee & Hayes PLLC
Microsoft Corporation
LandOfFree
Negotiating optimum parameters in a system of interconnected... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Negotiating optimum parameters in a system of interconnected..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Negotiating optimum parameters in a system of interconnected... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2575152