US 2004/0076122 A1Published application

Implementation of constraints to ensure deadlock avoidance in networks

AssigneeComplex Systems Research Limited

InventorVaughan William Wittorff

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method of determining where to place routing constraints known as cuts in a network to result in a no-loop network, and a method of implementing such constraints in a hierarchical network; to avoid deadlocks. The method of determining where to place cuts in a network to result in a no-loop network comprises an algorithm for numbering the nodes within the network which is used to determine where the cuts are to be placed. The method of implementing constraints in a hierarchical network to result in a no-loop network comprises an algorithm for independently determining cuts and meta-cuts for each peer group, and imposing the necessary routing constraints in the network.

Claims6

Dependent claims

A method of determining where to place cuts in a network to result in a no-loop network, wherein the network comprises a plurality of nodes and a plurality of arcs interconnecting said nodes, the method comprising the steps of:

a) selecting a starting node, numbering said starting node as node 1 and designating each of the arcs coming from node 1 as being directed outwardly from node 1;
b) selecting one of the nodes remaining unnumbered and numbering as node n+1, where n is the number of nodes that have already been numbered, according to the following criterion:
(1) being connected to the already numbered nodes by the highest number of arcs;
and if criterion (1) provides for several possible candidate nodes, then selecting from these candidate nodes according to the following criterion:
(2) having the highest number of arcs connected thereto;
and if this still provides for several possible candidate nodes, then selecting from these candidate nodes arbitrarily;
and designating each of the undirected arcs coming from node n+1 as being directed outwardly from node n+1;
c) repeating step b until all of the nodes are numbered;
and
d) placing cuts in the nodes between pairs of incoming arcs.

7 more elements

A method of implementing constraints in a hierarchical network wherein the hierarchical network comprises a plurality of nodes and a plurality of interconnecting arcs in the physical layer arranged into one or more peer groups, each peer group being considered as a logical group node in a higher level peer group in the hierarchy, with an arbitrary number of such hierarchical levels, the method comprising the steps, performed independently for each peer group, of:

a) placing cuts or meta-cuts in the nodes of a peer group such that said peer group is a no-loop network;
b) if meta-cuts were determined in step a), implementing the meta-cuts as routing constraints in the network, so that for any node in which a meta-cut has been placed between two arcs, controlled traffic entering by way of one of said two arcs is prevented from leaving the lower level peer group represented by the node, by way of the second of said two arcs, and vice versa.

Dependencies are inferred from the claim text.

Facts

Application: 10/684,745Filed 14 Oct 2003
Priority: AU 200295202314 Oct 2002
Published: 22 Apr 2004
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

H04L 45/02
Routing or path finding of packets in data switching networks: topology update or discovery
H04L 45/04
Topology update or discovery: interdomain routing, e.g. hierarchical routing
H04L 45/18
Routing or path finding of packets in data switching networks: loop-free operations
H04L
Digital communication

Family

US 7,532,584 B2Related patent
US 2004/0076122 A1This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key