Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
2007-10-09
2007-10-09
Ngo, Ricky Q. (Department: 2616)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S256000, C709S238000, C709S241000
Reexamination Certificate
active
10269749
ABSTRACT:
A method of searching for a shortest path from a single source node to a single destination node in a two dimensional computer network. The method is similar to Dijkstra shortest path algorithm (“Dijkstra”) in the way it builds a shortest path tree. However, instead of starting from the source node and searching through to the destination node as Dijkstra does, the method runs a shortest path search from both ends (i.e. source and destination) simultaneously or alternatively, until a shortest path tree from one end meets a shortest path tree from the other end at an intermediate node, and the concatenated path (source node intermediate node-destination node) satisfies a condition. Conditions other than those used by Dijkstra determine when the search should terminate, and whether the search has succeeded or failed. It has been verified that the new method requires less overhead and time than Dijkstra.
REFERENCES:
patent: 4597076 (1986-06-01), Bingham et al.
patent: 4905233 (1990-02-01), Cain et al.
patent: 5596719 (1997-01-01), Ramakrishnan et al.
patent: 6522630 (2003-02-01), Ooms et al.
patent: 6813272 (2004-11-01), An et al.
patent: 6990075 (2006-01-01), Krishnamurthy et al.
Mesh Network Topological Optimization And Routing, IBM Technical Disclosure Bulletin, May 1991, vol. 33 p. 67-69.
Tanenbaum, “Computer Networks,” 1996, pp. 38-41, 3rd ed, Prentice Hall, Upper Saddle River, NJ, US.
Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, 1959, pp. 269-271, vol. 1.
Aho et al. “The Design and Analysis of Computer Algorithms,” 1976, pp. 207-208.
Norton et al., “Thread Time The Multithreaded Programming Guide,” 1997, pp. 383-392.
Davis , Wright, Tremaine, LLP
Ngo Ricky Q.
Sinkantarakorn Pao
LandOfFree
Shortest path search method “Midway” does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Shortest path search method “Midway”, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shortest path search method “Midway” will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3840008