Non-blocking packet switching network with dynamic routing codes having incoming packets diverted and temporarily stored in processor inputs when network ouput is not available

• US 5,613,069 A
• Filed: 12/16/1994
• Issued: 03/18/1997
• Est. Priority Date: 12/16/1994
• Status: Expired due to Fees

• Current Assignee: Tony Walker
• Original Assignee: Tony Walker
• Inventors: Walker, Tony
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Luu, Le Hien
• Application Number:
  US08/357,335
• Time in Patent Office: 823 Days
• Field of Search: 370/54, 370/16, 370/60, 370/63, 370/94.3, 395/200.15, 395/200.02, 395/858, 395/182.02, 359/121
• US Class Current: 709/238
• 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/34 Source routing
• CPC Class Codes: H04L 49/10 characterised by the switching fabric construction
• CPC Class Codes: H04L 49/111 Switch interfaces, e.g. port details
• CPC Class Codes: H04L 49/15 Interconnection of switching modules
• CPC Class Codes: H04L 49/206 Real Time traffic
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/50 Overload detection or protection within a single switching element

Abstract

A data transmission network comprises a plurality of packet switches distributed throughout the network for transmitting data between a data source and destination. The destination of the incoming data is identified and a path created through the network to said destination based on the destination. The incoming data are assembled into packets. In the packets are included a plurality of routing codes defining the path through successive switches in the network. The packet switches for interpret the routing codes in the received packets and route the packets to the next switch until the destination is reached.

Claims

1. A data transmission network comprising:

a) a plurality of packet switching nodes distributed throughout the network for transmitting data packets between a data source and destination;

b) means for receiving incoming data and identifying the destination thereof;

c) means for identifying a path through the network to said destination;

d) means for assembling incoming data into packets and including in said packets a plurality of routing codes respectively defining the path through successive switches in the network;

e) switching means in said packet switching nodes for interpreting said routing codes in incoming packets, said switching means having network inputs and network outputs and processor inputs and processor outputs corresponding respectively to said network inputs and said network outputs, said switching means routing said incoming packets to a designated said network output in accordance with said routing codes if a valid routing code is interpreted and said designated output is available and otherwise diverting said incoming packets to a corresponding processor input; and

f) a processor in said packet switching nodes connected to said processor inputs and processor outputs of said switching means, said processor receiving said diverted packets over said processor inputs and temporarily storing said diverted packets, said processor sending the diverted packets with a valid routing code back to the network over said processor outputs when the designated network output becomes available.

2. A data transmission network as claimed in claim 1, wherein said switching nodes comprise means for successively stripping used routing codes from the packets as they flow through the network so that the first routing code in the packet always defines the outward path from the next switch node.

3. A data transmission network as claimed in claim 2, wherein said packets comprise a routing header field and a routing trailer field, said routing codes are included in said routing header field, and said switching nodes comprise means to insert further routing codes in said routing trailer field, said routing trailer codes in the trailer field identifying the path taken by the packets, whereby as the packets flow through the network the routing header and routing trailer fields are dynamically changed to indicate respectively the path to be taken and the path traversed of each packet.

4. A data transmission network as claimed in claim 3, wherein said packets contain a separator after the routing trailer and before the routing trailer.

5. A data transmission network as claimed in claim 4, wherein switching means diverts incoming packets to said processor if a said separator is encountered.

6. A data transmission network as claimed in claim 5, wherein said packets also contain control flags to indicate whether they contain user data or network management data, and said processor examines said control flags of packets diverted due an encountered separator, and if said processor determines that the incoming packet contains user data it discards it, and if said processor determines that the incoming packet contains network management data, it decodes the data and acts on it accordingly.

7. A data transmission network as claimed in claim 1, wherein a group of r of said plurality of inputs and outputs are allocated in each switching node to each said routing code, said r inputs and outputs thereby providing parallel channels for said packets through the network.

8. A data transmission network as claimed in claim 5, wherein said switching means comprise at least one hardware-implemented switch matrix unit connected to said network inputs and outputs via respective packet reception and transmission units, and to said processor inputs and outputs via packet-to-processor units and packet-from-processor units respectively.

9. A data transmission network as claimed in claim 8, wherein said packet-to-processor units comprise a data memory, a control unit for identifying the start and end of a packet, a processor interface, and an end-of-packet interrupt output.

10. A data transmission network as claimed in claim 8, wherein said packet-from-processor units comprise a data memory, a control unit for identifying the initial routing code and end of a packet, a processor interface, and an start-of-packet interrupt output.

11. A data transmission network as claimed in claim 8, wherein said switch matrix unit comprises a switch matrix with inputs and outputs, and a switch matrix controller controlling said switch matrix.

12. A data transmission network as claimed in claim 11, wherein said switch matrix controller comprises an interface logic unit and a port assignment array.

13. A data transmission network as claimed in claim 1, wherein said switching means comprise at least one hardware-implemented switch matrix connected to said inputs and outputs via respective packet reception and transmission units.

14. A data transmission network as claimed in claim 13, wherein said packet reception units comprise a de-framer, a byte accumulator, and a scanner for identifying bytes in the received packets.

15. A data transmission network as claimed in claim 13, wherein said packet transmission units comprise a FIFO memory, a byte serializer, and a framer.

16. A method of transmitting data over a network comprising the steps of:

a) receiving incoming data and identifying the destination thereof;

c) identifying a path through the network to said destination;

d) assembling incoming data into packets and including in said packets a plurality of routing codes defining the path through successive respective switching nodes in the network;

e) interpreting said routing codes in the incoming packets at each node in the network; and

f) if the interpreted routing codes are valid and a network output designated thereby is available, sending said packets to the designated output, and otherwise diverting said packets to a processor over a processor input corresponding to a network input over which the packets arrived, said processor sending the diverted packets with a valid routing code back to the network over processor outputs corresponding to when the designated network output becomes available.

17. A method as claimed in claim 16, wherein used routing codes are stripped from the packets as they flow through the network so that the first routing code in the packet always defines the outward path from the next switch node.

18. A method as claimed in claim 17, wherein said packets comprise a routing header field and a routing trailer field, said routing codes are included in said routing header field, and further routing codes identifying the path taken by the packets are inserted in said routing trailer field as the packets flow through the network, the routing header and routing trailer fields thereby being dynamically changed to indicate respectively the path to be taken and the path traversed of each packet.

19. A method as claimed in claim 18, wherein said packets contain a separator after the routing trailer and before the routing trailer.

20. A method as claimed in claim 19, wherein incoming packets are also diverted to said processor if a said separator is encountered.

21. A method as claimed in claim 20, wherein said packets also contain control flags to indicate whether they contain user data or network management data, and said processor examines said control flags of packets diverted due an encountered separator, and if said processor determines that the incoming packet contains user data it discards it, and if said processor determines that the incoming packet contains network management data, it decodes the data and acts on it accordingly.

22. A method as claimed in claim 16, wherein a group of r of said plurality of inputs and outputs are allocated in each switching node to each said routing code, said r inputs and outputs thereby providing parallel channels for said packets through the network.