Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-05-01
2002-10-01
Courtenay, III, St. John (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C717S124000
Reexamination Certificate
active
06460068
ABSTRACT:
The present invention is related to testing computer applications, and is more particularly related to applying principals of fractal geometry to testing applications in a distributed processing system.
BACKGROUND OF THE INVENTION
Fractal geometry is a field which studies self-similar graphic structures. A self-similar structure is characterized by a pattern of recursive reproduction of some basic structure. A good example is the Koch snowflake which can be built by the repeated substitution of some edges by a triangular form at every iteration. Although algorithms exist to realize the fractal expansion of geometrical forms, no study has been made of the application of this field to conventional computer graph theory. Since process graphs are best represented by tree-like structures, the present application testing concentrates on the fractal expansion of finite, connected, directed acyclic graphs. A simple fractal expansion has been used to test group services of a distributed processing system of the type disclosed in U.S. Pat. No. 5,699,501.
U.S. Pat. No. 5,430,658 issued Jul. 4, 1995 to Divinsky et al. for METHOD FOR CREATING SELF-GENERATING EMBROIDERY PATTERN, discloses a method for creating a self-generating embroidery design pattern, which may be provided alone or merged with an existing pattern by translation of fractal images into stitch patterns. The technique presented for creating stitch patterns appears to be a straight application of standard graphical rules for the generation for fractals.
U.S. Pat. No. 5,132,831 issued Jul. 21, 1992 to Shih et al. for ANALOG OPTICAL PROCESSING FOR THE CONSTRUCTION OF FRACTAL OBJECTS, discloses an analog optical processor for performing affine transformations and constructing fractal objects.
U.S. Pat. No. 5,396,413 issued Mar. 7, 1995 to Kaneko et al. for METHOD OF CONTROLLING AMENITY PRODUCTS OR ROTATING MACHINES, discloses applying fractal operation to motion of amenity products or rotating machines with a practical range and motion close to a natural phenomenon. This technique is not related to fractal geometry, but rather to fractal dimensions.
U.S. Pat. No. 4,789,933 issued Dec. 6, 1988 to Chen et al. for FRACTAL MODEL BASED IMAGE PROCESSING, discloses a medical diagnostic apparatus which generates medical diagnostic data which is reconstructed by an imager into an electronic image representation. The disclosed apparatus uses a time series with a fractal dimension wherein a filtered random generator is used to obtain a time series.
U.S. Pat. No. 5,430,812 issued Jul. 4, 1995 to Barnsley et al. of FRACTAL TRANSFORM COMPRESSION BOARD, discloses a digital image data compression apparatus including a controller circuit for receiving digital image data for processing the image data into blocks. Graphical geometry is used to map a nonfractal image into little fractal cells, and thus achieve compression, since the fractal rules take less encoding space. An image is divided into little pieces, and self similar cells are mapped to fractals from a template.
U.S. Pat. No. 5,486,280 issued Jan. 23, 1996 to Bullock, IV et al. for PROCESS FOR APPLYING CONTROL VARIABLES HAVING FRACTAL STRUCTURES, discloses a process and apparatus for the application of a control variable having a fractal structure to a body or process.
SUMMARY OF THE INVENTION
The present invention involves the application of Fractal Geometry principals (not fractal dimensions) to the field of Graph Theory. The Fractal Process Scheduler of the present invention solves the problem of exposing a distributed application to different scenarios for testing purposes. Typically, the tester develops a series of test cases, each of which address a specific scenario or protocol. This is the first part of the testing process. The second part is to schedule test cases for execution on a distributed system, in such a way that they will put the application being tested under considerable stress. In such a test environment it is desirable to run several of these test cases concurrently, but not strictly synchronized so that different time windows are created. Furthermore, this process must be easy to recreate, since re-creation will help the developers find and fix the defects found during the test run. These requirements rule out the most commonly used techniques for process scheduling. A simple fan out of the test cases will be strictly synchronized, and will not create different time windows. A simple serial execution will not create concurrency. The use of a random scheduler will not be able to re-create a scenario. The present state of the art is that the task of scheduling the test cases is left to the tester, who will have to code a process scheduler, which rivals in complexity with the test cases themselves. In the present invention, processes are defined as nodes in the graph, and the flow of control as edges. The scheduling algorithm is created by applying a fractal iteration to these nodes and edges. Nodes and edges are the building blocks in Graph Theory.
A primary object of the present invention is to provide a scheduler for testing applications in a distributed computing system wherein fractal expansion operations is applied to nodes and edges of a process scheduling chart graph to create deterministic sequences with very complex characteristics.
It is another object of the present invention to provide a scheduler wherein one sequences is a bounded simple fractal expansion.
It is another object of the present invention to provide a scheduler wherein another one of the sequences is a bounded compounded fractal expansion.
It is another object of the present invention to provide a scheduler wherein another one of the sequences is a bounded reciprocal fractal expansion.
It is another object of the present invention to provide a scheduler wherein another one of the sequences is a bounded recurrent fractal expansion.
It is another object of the present invention to provide a graphical user interface for use with a fractal process scheduler for testing applications of a distributed computing system.
It is another object of the present invention to provide a computer program product for scheduling processes of an application to be tested to nodes of a distributed processing system using complex fractal expansions.
It is another object of the present invention to provide a method for scheduling processes of an application to be tested to nodes of a distributed processing system using complex fractal expansions.
The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of the preferred embodiment of the invention as illustrated in the drawings.
REFERENCES:
patent: 4789933 (1988-12-01), Chen et al.
patent: 5132831 (1992-07-01), Shih et al.
patent: 5396413 (1995-03-01), Kaneko et al.
patent: 5430658 (1995-07-01), Divinsky et al.
patent: 5430812 (1995-07-01), Barnsley et al.
patent: 5486280 (1996-01-01), Bullock, IV et al.
patent: 5909544 (1999-06-01), Anderson, II et al.
patent: 6014760 (2000-01-01), Silva et al.
patent: 6128754 (2000-10-01), Graeve et al.
Courtenay III St. John
Cutter Lawrence D.
Gonzalez Floyd A.
Nguyen Van H.
LandOfFree
Fractal process scheduler for testing applications in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fractal process scheduler for testing applications in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fractal process scheduler for testing applications in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2962628