Communications network

• US 6,714,552 B1
• Filed: 02/25/1999
• Issued: 03/30/2004
• Est. Priority Date: 08/28/1996
• Status: Expired due to Term

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Cotter, David
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): ABELSON, RONALD B
• Application Number:
  US09/029,197
• Time in Patent Office: 1,860 Days
• Field of Search: 370/351, 370/238, 370/216, 370/228, 370/242, 370/244, 370/248, 370/390, 370/355, 370/408, 370/406, 370/256, 370/389, 370/392, 709/241, 709/238-239, 712/11, 712/25, 712/28, 359/135-139
• US Class Current: 370/406
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04Q 11/0005 Switch and router aspects
• CPC Class Codes: H04Q 2011/0024 using space switching
• CPC Class Codes: H04Q 2011/0033 using time division switching
• CPC Class Codes: H04Q 2011/0039 Electrical control
• CPC Class Codes: H04Q 2011/0052 Interconnection of switches
• CPC Class Codes: H04Q 2011/0073 Provisions for forwarding or routing, e.g. lookup tables
• CPC Class Codes: H04Q 2011/009 Topology aspects

Abstract

A communications network, suitable, for example, for linking computer processors, is formed from a number of nodes and links. The nodes and links are configured as a multiplicity of directed trails. Each directed trail spans some only of the nodes, but in combination the directed trails span every node of the network. Packets are routed through the network by selecting the appropriate one of the directed trails which links the source node and destination node, and by outputting the packet at the source node onto the selected trail. The nodes throughout the network may switch between predetermined and prescheduled switching states, and a given trail may be selected by choosing appropriately the time slot in which the packet is put onto the network. The network may be a photonic network carrying optical packets.

Claims

1. An optical communications network, comprising:

a) means for selecting a time slot for a packet in dependence upon the desired path for the packet through the network;

b) means for outputting the packet onto the network at a source node in the time slot selected by the means for selecting;

c) means for switching repeatedly with a fixed periodicity the routing states of a multiplicity of routing nodes;

d) at the network nodes, means for switching the packet to different outputs according to the routing state of the respective node in the time slot in which the packet arrives at the node; and

e) means for receiving the packet at a destination node.

2. A method of routing an optical packet from a source node to a destination node in an optical communications network, comprising:

a) selecting a time slot for a packet in dependence upon the desired path for the packet through the network;

b) outputting the packet onto the network at a source node in the time slot selected in step (a);

c) switching repeatedly with a fixed periodicity the routing states of a multiplicity of routing nodes;

d) as the packet traverses the network, at the different nodes switching the packet to different outputs according to the routing state of the respective node in the time slot in which the packet arrives at the node; and

e) receiving the packet at a destination node.

3. A method of routing a packet in a communications network, the network comprising a multiplicity of nodes and links, and wherein the nodes and links are configured as a multiplicity of directed trails, each directed trail linking only some of the multiplicity of nodes and the directed trails in combination spanning every node of the network, the method comprising the steps of:

a) selecting a directed trail T from the multiplicity of directed trails in dependence upon the destination of a packet, the selected trail including the source node and destination node of the packet;

b) outputting the packet at the source node onto the selected one of the multiplicity of directed trails;

c) reading, at each intermediate node traversed by the packet, a destination address carried in the packet; and

d) if the packet is addressed to another node, forwarding the packet in a direction that is predetermined and independent of any address information carried by the packet;

wherein each directed trail in the network is a subgraph of at least one closed directed trail and includes a-directed cycle or union of a plurality of connected directed cycles from a link-disjoint directed-cycle decomposition of the network.

4. A method according to claim 3, wherein the packet is an optical packet carried on a photonic network.

5. A method according to claim 3,

wherein the step of selecting a directed trail T includes synchronizing the initial dispatch of the packet with prescheduled switching at an intermediate node.

6. A method according to claim 3,

wherein the nodes switch in synchronism throughout the network between pre-scheduled predetermined switching states.

7. A method of routing a packet in a communications network, the network comprising a multiplicity of nodes and links, and wherein the nodes and links are configured as a multiplicity of directed trails, each directed trail linking only some of the multiplicity of nodes and the directed trails in combination spanning every node of the network, the method comprising the steps of:

a) selecting a directed trail T from the multiplicity of directed trails in dependence upon the destination of a packet, the selected trail including the source node and destination node of the packet;

b) outputting the packet at the source node onto the selected one of the multiplicity of directed trails;

c) reading, at each intermediate node traversed by the packet, a destination address carried in the packet; and

d) if the packet is addressed to another node, forwarding the packet in a direction that is predetermined and independent of any address information carried by the packet;

wherein switching occurs at a point of connection between cycles from a link-disjoint directed-cycle decomposition of the network.

8. A method according to claim 7, wherein the packet is an optical packet carried on a photonic network.

9. A method according to claim 7,

wherein the step of selecting a directed trail T includes synchronizing the initial dispatch of the packet with prescheduled switching at an intermediate node.

10. A method according to claim 7,

wherein the nodes switch in synchronism throughout the network between pre-scheduled pre-determined switching states.

11. A method of routing a packet in a communications network, the network comprising a multiplicity of nodes and links, and wherein the nodes and links are configured as a multiplicity of directed trails, each directed trail linking only some of the multiplicity of nodes and the directed trails in combination spanning every node of the network, the method comprising the steps of:

a) selecting a directed trail T from the multiplicity of directed trails in dependence upon the destination of a packet, the selected trail including the source node and destination node of the packet;

b) outputting the packet at the source node onto the selected one of the multiplicity of directed trails;

c) reading, at each intermediate node traversed by the packet, a destination address carried in the packet; and

d) if the packet is addressed to another node, forwarding the packet in a direction that is predetermined and independent of any address information carried by the packet;

wherein the nodes switch in synchronism throughout the network between pre-scheduled pre-determined switching states; and

a timing sequence for the prescheduled switching of intermediate nodes comprises a frame divided into a plurality of time slots and a source node outputs a packet onto the network in a selected one of a plurality of time slots within a timing frame, and the length of the link between successive nodes in a trail is such that a packet leaving one node in a first time slot arrives at the next successive node in a second time slot.

12. A method according to claim 11, wherein the length of the link is such that on travelling between the successive nodes the packet is advanced or retarded by one time slot.

13. A method according to claim 11, wherein the packet is an optical packet carried on a photonic network.

14. A method according to claim 11,

wherein the step of selecting a directed trail T includes synchronizing the initial dispatch of the packet with prescheduled switching at an intermediate node.

15. A communications network, comprising:

a) a multiplicity of nodes including at least one source node, at least one destination node, and a plurality of intermediate links therebetween, the nodes and the links being configured as a multiplicity of directed trails, each directed trail spanning some of the multiplicity of nodes, the multiplicity of directed trails in combination spanning every node of the network, each source node being connected to each destination node by a respective directed trail;

b) means for selecting a directed trail T from the multiplicity of directed trails in dependence upon the destination of a packet, the selected trail including the source node and destination node of the packet;

c) means for outputting the packet at the source node onto the selected one of the multiplicity of directed trails;

d) means, associated with each intermediate node, for reading a destination address carried by an arriving packet; and

e) means for determining if the arriving packet is addressed to an intermediate node, and if the packet is addressed to another node, means arranged to forward the packet in a direction that is predetermined and independent of any address information carried by the packet;

wherein each directed trail in the network is a subgraph of at least one closed directed trail and includes a directed cycle or union of a plurality of connected directed cycles from a link-disjoint directed-cycle decomposition of the network.

16. A communications network as in claim 15, further comprising an input for receiving packets for transmission on the network.

17. A communications network according to claim 15, wherein the network is a photonic network arranged to carry optical packets.

18. A communications network according to claim 15,

wherein a source node is arranged to synchronize the initial dispatch of a packet with prescheduled switching at an intermediate node.

19. A network according to claim 15,

wherein the nodes are arranged to switch in synchronism throughout the network between switching states that are pre-scheduled and pre-determined.

20. A communications network, comprising:

a) a multiplicity of nodes including at least one source node, at least one destination node, and a plurality of intermediate links therebetween, the nodes and the links being configured as a multiplicity of directed trails, each directed trail spanning some of the multiplicity of nodes, the multiplicity of directed trails in combination spanning every node of the network, each source node being connected to each destination node by a respective directed trail;

b) means for selecting a directed trail T from the multiplicity of directed trails in dependence upon the destination of a packet, the selected trail including the source node and destination node of the packet;

c) means for outputting the packet at the source node onto the selected one of the multiplicity of directed trails;

d) means, associated with each intermediate node, for reading a destination address carried by an arriving packet; and

e) means for determining if the arriving packet is addressed to an intermediate node, and if the packet is addressed to another node, means arranged to forward the packet in a direction that is predetermined and independent of any address information carried by the packet;

wherein switching occurs at a point of connection between cycles from a link-disjoint directed-cycle decomposition of the network.

21. A communications network as in claim 20, further comprising an input for receiving packets for transmission on the network.

22. A communications network according to claim 20, wherein the network is a photonic network arranged to carry optical packets.

23. A communications network according to claim 20, wherein the nodes are arranged to switch in synchronism throughout the network between switching states that are pre-scheduled and pre-determined.

30. A communications network according to claim 20, wherein a source node is arranged to synchronize the initial dispatch of a packet with prescheduled switching at an intermediate node.

24. A communications network, comprising:

a) a multiplicity of nodes including at least one source node, at least one destination node, and a plurality of intermediate links therebetween, the nodes and the links being configured as a multiplicity of directed trails, each directed trail spanning some of the multiplicity of nodes, the multiplicity of directed trails in combination spanning every node of the network, each source node being connected to each destination node by a respective directed trail;

b) means for selecting a directed trail T from the multiplicity of directed trails in dependence upon the destination of a packet, the selected trail including the source node and destination node of the packet;

c) means for outputting the packet at the source node onto the selected one of the multiplicity of directed trails;

d) means, associated with each intermediate node, for reading a destination address carried by an arriving packet; and

e) means for determining if the arriving packet is addressed to an intermediate node, and if the packet is addressed to another node, means arranged to forward the packet in a direction that is predetermined and independent of any address information carried by the packet;

wherein the nodes are arranged to switch in synchronism throughout the network between switching states that are pre-scheduled and pre-determined;

a timing sequence for the prescheduled switching of intermediate nodes comprises a frame divided into a plurality of time slots;

a source node is arranged to output a packet onto the network in a selected one of a plurality of time slots within a timing frame; and

the length of the directed link between successive nodes in a trail is such that a packet leaving one node in a first time slot arrives at the next successive node in a second time slot.

25. A communications network as in claim 24, further comprising an input for receiving packets for transmission on the network.

26. A communications network according to claim 24, wherein the network is a photonic network arranged to carry optical packets.

27. A communications network according to claim 24, wherein a source node is arranged to synchronize the initial dispatch of a packet with prescheduled switching at an intermediate node.

28. A communications network according to claim 24, wherein the nodes are arranged to switch in synchronism throughout the network between switching states that are pre-scheduled and pre-determined.

29. In a communications network having a plurality of nodes, including a source node and a destination node, a plurality of links connecting the nodes, the nodes and links having a configuration such that they form a plurality of directed trails, the configuration of the nodes and links being time-dependent such that paths traced by the directed trails change sequentially over time, each directed trail linking only some of the nodes, the directed trails in combination spanning every node of the network, the method of routing a packet comprising:

emitting a packet from a source node;

wherein time of the emission of the packet being dependent upon the destination node where the packet is to be received; and

the configuration of the nodes and links changes with time according to a predetermined cycle.