Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
2007-03-06
2007-03-06
Pham, Chi (Department: 2616)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S376000, C370S386000, C370S539000, C340S002280
Reexamination Certificate
active
10147446
ABSTRACT:
A processor is programmed to reduce a problem of adding a new connection to a time-space-time (TST) switch of a communication network into a problem of graph theory, and to solve the problem using a heuristic instead of an exact algorithm. A solution, if provided by the heuristic, is used to rearrange the connections in the TST switch. Several embodiments of such a programmed processor reduce a connection rearrangement problem of a TST switch into any one of the NP-complete problems (such as the vertex coloring problem or the boolean satisfiability (SAT) problem). In some such embodiments, the processor is programmed based on the Brélaz heuristic to find a solution to the vertex coloring problem. In other embodiments, other heuristics, such as a genetic algorithm, may be used.
REFERENCES:
patent: 3736381 (1973-05-01), Johnson et al.
patent: 5276425 (1994-01-01), Swanson et al.
patent: 5301055 (1994-04-01), Bagchi et al.
patent: 5450074 (1995-09-01), Yoshifuji
patent: 5634004 (1997-05-01), Gopinath et al.
patent: 5889775 (1999-03-01), Sawicz et al.
patent: 5987027 (1999-11-01), Park et al.
patent: 6085216 (2000-07-01), Huberman et al.
patent: 6192475 (2001-02-01), Wallace
patent: 6327253 (2001-12-01), Frink
patent: 6950418 (2005-09-01), Young et al.
patent: 2002/0124239 (2002-09-01), Nelson
patent: 2003/0161268 (2003-08-01), Larsson et al.
V.E. Benes, “On Rearrangeable Three -Stage Connecting Networks”, The Bell System Technical Journal vol. XLI, Sep. 1962, No. 5, pp. 1481-1491.
M.C. Paull, “Reswitching of Connection Networks”, The Bell System Technical Journal, 41 (3), May 1962, pp. 833-853.
Daniel Brélaz, “New Methods to Color the Vertices of a Graph”, Communication of the ACM, Apr. 1979, vol. 22, No. 4, pp. 251-256.
A.E. Eiben, J.K. van der Hauw, “Graph Coloring with Adaptive Genetic Algorithms”, Journal of Heuristics, 4(1), 1998, pp. 1-43, www.wi.leidenuniv.nl/TechRep/tr96-11.html.
Hantao Xhang et al., “Implementing the Davis-Putnam Method”, Journal of Automatic Reasoning, 24(1/2) 2000, pp. 1-23.
C. Clos, “A Study of Non-blocking Switching Networks”, The Bell Systems Technical Journal, 32:406-424, Mar. 1953.
V. E. Benes, “Mathematical Theory of Connecting Networks and Telephone Traffic,” Academic Press, 1965.
Y. Yang, “Nonblocking Broadcast Switching Networks,” JSSE Transactions on Computers, vol. 40, No. 9, Sep. 1991, pp. 1005-1015.
S. Skiena, “Finding a Vertex Coloring.” §5.5.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 214-215, 1990.
Davis, M. and Putnam, H. “A Computing Procedure for Quantification Theory”, Journal of the Association for Computing Machinery, 7(3) (Jul. 1960), 201-215.
Maher Ali and Jitender S. Deogun, “Cost-Effective Implementation of Multicasting In Wavelength-Routed Networks,” IEEE Journal of Lightwave Technology, vol. 18, No. 12, Dec. 2000, pp. 1628-1638.
File History of U.S. Appl. No. 10/199,996 by Meenaradchagan Vishnu entitled “Arbiter for an Imput Buffered Communication Switch”.
Calix Networks, Inc.
Jagannathan Melanie
Pham Chi
Silicon Valley Patent & Group LLP
LandOfFree
Connection rearrangement in communication switches does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Connection rearrangement in communication switches, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Connection rearrangement in communication switches will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3769761