Method and device for network reconfiguration

• US 20040257993A1
• Filed: 03/26/2004
• Published: 12/23/2004
• Est. Priority Date: 03/26/2003
• Status: Abandoned Application

• Current Assignee: Simula Research Laboratory AS
• Original Assignee: Simula Research Laboratory AS
• Inventors: Duato, Jose, Pinkston, Timothy, Lysne, Olav
• Application Number:
  US10/809,376
• Publication Number:
  US 20040257993A1
• Time in Patent Office: Days
• US Class Current: 370/230
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/566 Routing instructions carried by the data packet, e.g. active networks

Abstract

The present invention describes a method and system that allows a network to alter its routing strategy from one routing function to another while the network is up and running. For networks with link level backpressure, the method provides a deadlock free transition between the routing strategies. A variant of the method also guarantees that all packets will be delivered in order.

Claims

1. Method for deadlock free altering of a network routing from a first routing function R_old, defining an established connection between a plurality of communication input ports I₁, . . . ,I_n and output ports O₁, . . . ,O_m, in a network element, to a second routing function R_new, defining an new connection between the said input and output ports, for execution by the network element for transmitting and receiving data packets, said method comprising:

(1) for each input port I_i, performing the following steps;

(1a) applying the first routing function R_old for the input port,

(1b) receiving a token on an input port I_i,

(1c) applying the second routing function R_new for the input port I_i,

(1d) forwarding data packets to every output port O_j associated with the input port I_i according to the second routing function R_new, provided that the output port O_j has transmitted the token,

(2) for each output port O_j, performing the following steps;

(2a) determining if the token has been received on all input ports associated with the output port O_j according to the first routing function R_old,

(2b) transmitting the token on the output port O_j when the token has been received on all said input ports.

2. Method according to claim 1, wherein the network element is a switch.

3. Method according to claim 1 or 2, wherein the token is included in a data packet.

4. Method according to claim 1, wherein the method is applied to deterministic routing functions.

5. Method according to claim 1, wherein the method is applied to adaptive routing functions.

6. Method according to claim 1, wherein the method is applied to source routing.

7. Method according to claim 5, wherein if the adaptive method gives rise to a cyclic dependency graph, the graph is pruned into a non-cyclic one before the method is applied.

8. Method according to claim 1, wherein the method is applied to only parts of a complete network.

9. Network element, comprising

a plurality of output ports for transmitting data packets to other network elements in a network,

a plurality of input ports for receiving data packets from other network elements in the network,

a processing device,

a memory,

characterized in that the processing device is arranged to perform a method according to claim 1.

10. Network element according to claim 9, wherein said routing functions are implemented as tables stored in said memory.

11. Network element according to one of the claims 9 or 10, wherein said memory comprises computer program instructions arranged to perform said method when executed by said processing device.

12. Computer network system, comprising a number of network elements according to claim 9.

13. Computer program, embodied on a storage medium or in a memory, or carried by a propagated signal, for execution by a processing device in a network element, characterized in that the program comprises a set of instructions arranged to perform a method according to claim 1 when executed by the processing device in the network element.