Fast packet switching system

• US 4,494,230 A
• Filed: 06/25/1982
• Issued: 01/15/1985
• Est. Priority Date: 06/25/1982
• Status: Expired due to Term

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T, Inc.
• Inventors: Turner, Jonathan S.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Chin, Wellington
• Application Number:
  US06/393,112
• Time in Patent Office: 935 Days
• Field of Search: 370/60, 370/94, 370/58
• US Class Current: 370/409
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• 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 49/10 characterised by the switching fabric construction
• CPC Class Codes: H04L 49/118 Address processing within a device, e.g. using internal ID or tags for routing within a switch
• CPC Class Codes: H04L 49/1507 Distribute and route fabrics, e.g. sorting-routing or Batcher-Banyan
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/501 Overload detection
• CPC Class Codes: H04L 49/555 Error detection

Abstract

A communication method and packet switching system in which packets comprising logical addresses and voice/data information are communicated through the system by packet switching networks which are interconnected by high-speed digital trunks with each of the latter being directly terminated on both ends by trunk controllers. During initial call setup of a particular call, central processors associated with each network in the desired route store the necessary logical to physical address information in the controllers which perform all logical to physical address translations on packets of the call. Each network comprises stages of switching nodes which are responsive to the physical address associated with a packet by a controller to communicate this packet to a designated subsequent node. The nodes provide for variable packet buffering, packet address rotation techniques, and intranode and internode signaling protocols. Each packet has a field which is automatically updated by the controllers for accumulating the total time delay incurred by the packet in progressing through the networks. Each processor has the capability of doing fault detection and isolation on the associated network, trunks, and controllers by the transmission of a single test packet. The testing is done solely in response to the test packet and no preconditioning of controllers or networks is necessary.

Claims

1. A fast packet switching system for switching packets for a plurality of messages from a plurality of transmission links comprising;

a packet switching network having a plurality of interconnected packet switch nodes,

a plurality of distributed controllers each for interfacingly connecting an individual one of said transmission links to one of said packet switch nodes and comprising,

memory means for storing translation information for controlling the routing of packets of one of said messages communicated over said one of said links through a plurality of said switch nodes to another of said controllers, and

means for concatenating translation information stored in said memory means with said packets of said one of said messages to produce a plurality of address bits,

and

said one of said switch nodes comprising

a plurality of input conductors,

a plurality of output conductors,

a plurality of output conductors,

means responsive to a predetermined number of said plurality of address bits from one of said input conductors for routing a received packet of said one of said messages from said one of said input conductors to one of said output conductors defined by said predetermined number of address bits, and

means for repositioning said predetermined number of address bits in said plurality of address bits in the routing of said received packet to said defined one of said output conductors.

2. The invention of claim 1 wherein said plurality of transmission links comprises digital transmission links;

said predetermined number of said address bits comprise the most significant address bits in said plurality of address bits; and

said repositioning means relocates said most significant bits to a lesser significant bit position in said plurality of address bits and lesser significant bits in said plurality of address bits to the most significant bit position.

3. The invention of claim 1 wherein said plurality of transmission links comprise digital transmission links, each said packet comprises a plurality of bit signals, and said one of said switching nodes further comprises

buffer means for storing bit signals of said received packet;

means responsive to a receipt of a packet communication available signal from said one of said defined output conductors for routing the then stored bit signals in said buffer means and said repositioned plurality of address bits to said defined one of said output conductors.

4. The invention of claim 3 wherein said one of said defined output conductors is connected to another of said switching nodes which comprises

buffer means for storing bit signals of said packets;

and

means responsive to said buffer means of said other node having present capacity to receive one of said packets for transmitting said packet communications available signal.

5. A fast packet switching system for switching plural bit signal packets of a plurality of messages from a plurality of digital transmission links comprises;

a packet switching network comprising a plurality of interconnected packet switch nodes;

a plurality of distributed controllers each for interfacingly connecting an individual one of said transmission links to one of said packet switch nodes and comprising;

memory means for storing translation information for controlling the routing of packets of one of said messages communicated over said one of said links through a subset of said switch nodes to another of said controllers; and

means for concatenating translation information stored in said memory means with packets of one of said messages to produce a plurality of address bits,

said one of said switch nodes comprising;

a plurality of output conductors for transmission of packets

buffer means for variably storing bit signals of said received packet; and

means controlled by said address bits responsive to a receipt of a packet communication available signal from another one of said switching nodes for designating one of said output conductors to route the then and subsequently stored bit signals of said received packet further through said network to said other one of said switching nodes.

6. The invention of claim 5 wherein said one of said switch nodes further comprises;

means for repositioning a predetermined number of said plurality of address bits in the routing of said stored bit signals of said received packet further through said network.

7. The invention of claim 6 wherein said other one of said switch nodes further comprises

buffer means for storing bit signals of said packets;

and

means responsive to said buffer means of said other node having present capacity to receive one of said packets for transmitting said packet communications available signal.

8. A packet switching system for switching packets for a plurality of messages from a plurality of digital transmission links comprising:

a packet switching network having a plurality of interconnected switching nodes;

a plurality of distributed controllers each for interfacingly connecting an individual one of said transmission links to one of said switching nodes;

processor means responsive to a receipt of one of said packets for one of said messages on a calling one of said controllers for generating translation information for routing other of said packets of said one of said messages through said network to a called one of said controllers;

processor controller for forming a first control packet for communicating the generated translation information to said calling one of said controllers via said network;

memory means in said calling one of said controllers responsive to said first control packet for storing translation information generated by said processor means for controlling the routing of said other packets of said one of said messages through said switching network to said called one of said controllers; and

said processor means comprises validity checking means for effecting a reading of the translation information stored in said memory means of said calling one of said controllers by transmission of a second control packet via said network.

9. The invention of claim 8 further comprising:

memory means in said called one of said controllers for storing translation information generated by said processor means for controlling a routing of packets of another one of said messages through said switching network to said calling one of said controllers.

10. A fast packet switching system for switching packets for a plurality of messages from a plurality of digital transmission links comprising:

a packet switching network having a plurality of interconnected packet switch nodes,

a plurality of distributed controllers each for interfacingly connecting an individual one of said transmission links to one of said packet switch nodes and comprising,

memory means for storing translation information for controlling the routing of packets of one of said messages communicated over said one of said links through a plurality of said switch nodes to another of said controllers, and

means for concatenating translation information stored in said memory means with said packets of said one of said messages to produce a plurality of address bits, and

said one of said switch nodes comprising

a plurality of input conductors,

a plurality of output conductors,

means responsive to a packet communication available signal and a predetermined number of said plurality of address bits from one of said input conductors for routing a received packet of said one of said messages from said one of said input conductors to one of said output conductors defined by said predetermined number of address bits, and

said one of said defined output conductors connected to another of said switching nodes which comprises

buffer means for variably storing bit signals of said packets;

means responsive to said buffer means of said other node having present capacity to partially receive one of said packets for transmitting said packet communications available signal; and

means for repositioning said predetermined number of address bits in said plurality of address bits in the routing of said received packet to said defined one of said output conductors.

11. The invention of claim 10 wherein

said predetermined number of said address bits comprise the most significant address bits in said plurality of address bits;

and

said repositioning means relocates said most significant bits to a lesser significant bit position in said plurality of address bits and lesser significant bits in said plurality of address bits to the most significant bit position.

12. The invention of claim 11 wherein said one of said switching nodes further comprises

storage means for storing said received packet;

means responsive to a receipt of said packet communication available signal from said one of said defined output conductors for routing the then stored received packet in said storage means to said defined one of said output conductors.

13. A packet switching system for communicating a message comprising a plurality of information packets and a call set-up packet, each of said information packets comprising logical address data, said system comprising:

processor means responsive to a receipt of said call set-up packet for generating another logical address and physical address translation information;

switching network means for switching said information packets to a destination;

distributed controller means for communicating said information packets to said network means and comprising

means for storing the other logical address and physical address translation information generated by said processor means;

means responsive to a receipt of one of said information packets for inserting the other logical address into said one of said information packets; and

means responsive to a receipt of one of said information packets for concatenating the stored physical address information in said storing means with said one of said information packets.

14. The invention of claim 13 wherein said controller means comprises means responsive to said receipt of said call set-up packet for controlling the switching of said set-up packet through said network means to said processor means.

15. The invention of claim 13 wherein said switching network means comprises a plurality of interconnected switching nodes;

one of said switching nodes comprising

a plurality of input conductors;

a plurality of output conductors;

means responsive to said logical and physical address information concatenated with said one of said information packets from one of said input conductors for routing said one of said information packets from said one of said input conductors to one of said output conductors defined by said physical address information.

16. A packet switching system for the transmission of packets with each of said packets comprising a logical address field, a data field and flag fields, said switching system comprises

customer terminals interconnected by switching networks;

transmission facilities for communicating packets from said customer terminals;

interface facilities connecting said transmission facilities to said networks;

one of said interface facilities comprises

means responsive to said logical address in a received one of said packets to transform said logical addresses to a network address for transmission of said received one of said packets through a connected network;

and

means responsive to said received one of said packets to send a request signal to said connected network;

said connected network being responsive to said request signal to transmit an enable signal to said one of said interface facilities upon said connected network having present storage capacity to start the storage of said received one of said packets;

said connected network being responsive to said network address to route said received one of said packets to another one of said interface facilities; and

one of said customer terminals upon receiving said one of said packets performing the error recovery if an error resulted in transmission through said packet system.

17. The invention of claim 16 wherein said one of said interface facilities further comprises means to assemble a new packet containing said network address and said original packet for transmission through said connected network.

18. The invention of claim 16 wherein said one of said interface facilities further comprises a memory means for storing said received one of said packets;

means responsive to the storage of said received one of said packets to transmit said request signal; and

means responsive to a receipt of said enable signal to effect the transmission of the stored packet to said connected network.

19. The invention of claim 18 wherein said received one of said packets is transmitted at a lower transmission rate on said transmission facility connected to said one of said interface facilities and at a higher rate from said one of said interface facilities to said network.

20. The invention of claim 16 wherein said transmission facilities include high-speed digital transmission facilities.

21. The invention of claim 18 wherein said memory means entirely stores said one of said packets before transmission to said network.

22. The invention of claim 18 wherein said connected network comprises switching elements, one of said switching elements being connected to said one of said interface facilities and comprising a variable storage means for storing said received one of said packets and input control means responsive to a receipt of said request signal to transmit said enabling signal upon said variable storage means having present capacity to store said received one of said packets.

23. The invention of claim 22 wherein said variable storage means comprises a shift register.

24. The invention of claim 16 wherein said connected network comprises switching elements, one of said elements being responsive to said received one of said packets for requesting by a signaling protocol permission to transmit said received one of said packets to other ones of said switching elements.

25. The invention of claim 16 wherein all of said packets transmitted from a transmitting customer terminal to a destination customer terminal are routed sequentially through said system over a bidirectional virtual circuit extending therebetween.

26. A packet switching system comprising a switching network terminating a plurality of interface facilities interfacing said network with packet switching communication links;

said network comprising a plurality of switching nodes;

one of said interface facilities comprising means responsive to a receipt of a packet comprising a plurality of bits at a first predetermined rate for storing the entire packet and means responsive to a receipt of a transmission available signal from said network for transmitting the stored packet to one of said switching nodes at a second predetermined rate; and

said one of said switching nodes comprising a variable buffering means for storing said bits of said received packet and means responsive upon the receipt of a transmission enable signal from a downstream one of said switching nodes for bypassing said buffering means immediately to effect the transmission of the stored bits of said received packet to said downstream one of said switching nodes.

27. The invention of claim 26 wherein said one of said interface facilities comprises memory means for storing said packet, receive means responsive to the receipt of said packet from one of said packet switching communication links at said first predetermined rate for storing the entire packet in said memory means;

and

transmitter means responsive to the storage of said packet in said memory means to effect the transmission therefrom of the stored packet at said second predetermined rate to said first one of said switching nodes upon a receipt of said transmission available signal.

28. The invention of claim 27 wherein said transmitter means further comprises means responsive to said storage of said packet in said memory means to transmit a request signal to said one of said switching nodes;

and

said one of said switching nodes further comprising means responsive to said request signal to transmit said transmission available signal upon said variable buffering means being capable of storing said bits of said packet.

29. The invention of claim 28 wherein said packet comprises an address field for address information designating downstream switching nodes in said network through which said packet is to be transmitted.

30. The invention of claim 29 wherein said one of said switching nodes further comprises means responsive to said information signals in said address field of said packet immediately to commence transmission of said packet to a designated first one of said downstream switching nodes upon having received another transmission available signal from said first one of said downstream switching nodes.

31. The invention of claim 30 wherein said first mentioned one of said switching nodes further comprises means for storing said transmission available signal from said first one of said downstream nodes.

32. The invention of claim 31 wherein said first-mentioned one of said switching nodes further comprises means for interrogating storing means in response to said address information of said packet to determine whether said transmission available signal had previously been received.

33. The invention of claim 32 wherein said interrogating means comprising means for reading said packet from said memory means and means responsive to said read packet to assemble a switch packet for transmission to said first-mentioned one of said downstream switching nodes.

34. The invention of claim 27 wherein said receive means further comprising means for detecting errors in said packet and means responsive to a detected error to inhibit the storage of said packet in said memory means.

35. A packet switching for the transmission of packets for customer terminals with flow control and error recovery functions performed by the originating and destination ones of said customer terminals, each of said packets comprising a logical address field, a data field and flag fields, said switching system comprises:

switching networks;

high speed transmission facilities;

interface facilities connecting said transmission facilities to said networks; and

each of said interface facilities comprising means for receiving said packets at a first predetermined rate and means for retransmitting said received packets at a second predetermined rate higher than said first predetermined rate to said connected network;

one of said interface facilities responsive to the logical address field of one of said packets for forming a switch packet comprising a plurality of address bits and said one of said packets;

said connected network comprises a plurality of interconnected packet switch nodes with one of said switch nodes interconnected to one of said interface facilities and comprising a plurality of output conductors,

storage means for variably storing one of said packets and said plurality of address bits received from said one of said interface facilities;

means responsive to a predetermined number of said plurality of address bits from said one of said interface facilities and a packet communication available signal from one of said output conductors defined by said predetermined number of address bits for immediately routing said received packet both from said variable storing means and from said one of said interface facilities to said one of said output conductors.

36. The invention of claim 35 wherein each of said transmission facilities comprising a high speed digital transmission facility.

37. The invention of claim 36 wherein each of said packets further comprising error check signals and one of said interface facilities is responsive to one of said packets for calculating error signals from said one of said packets;

said one of said interface facilities comprising means for comparing said error check signals with said error signals;

said one of said interface facilities further comprising an inhibit means responsive to said comparing means for inhibiting the transmission of said one of said packets to said connected network upon said error check signals not being identical to said error signals.

38. The invention of claim 36 wherein said one of said interface facilities comprises memory means for storing said one of said packets, receive means responsive to the receipt of said one of said packets from one of said transmission facilities for storing said one of said packets in said memory means;

transmitter means responsive to the complete storage of said one of said packets in said memory means to effect the transmission of said one of said packets to said connected network.

39. The invention of claim 38 wherein said one of said packets further comprising error check signals and said receive means comprising means responsive to said one of said packets to generate error signals from said one of said packets;

and

inhibit means responsive to said one of said packets to compare said error check signals and said error signals for inhibiting the storage of said one of said packets upon said error check signals and said error signals not being identical.

40. The invention of claim 39 wherein said transmitter means comprising means responsive to said logical address in said one of said packets to transform said logical address to a network address for transmission of said one of said packets through said connected network.

41. The invention of claim 40 wherein said connected network comprises means responsive to said network address to route said one of said packets to another one of said interface facilities.

42. A packet switching system for communicating a message comprising a plurality of information packets and a call set-up packet, each of said information packets comprising logical address data, said system comprising:

processor means responsive to a receipt of said call set-up packet for generating another logical address and physical address translation information;

switching network means for switching said information packets to a destination;

plurality of distributed controller means for bidirectionally communicating received information packets to said network means and each of said distributed controller means comprising

means for storing the other logical address and physical address translation information generated by said processor means;

means for inserting said other logical address into one of said information packets; and

means responsive to a receipt of said one of said information packets for concatenating the stored physical address information in said storing means with said one of said information packets.

43. A fast packet switching system for switching packets for a plurality of messages from a plurality of digital transmission links comprising:

a packet switching network having a plurality of interconnected packet switch nodes,

one of said switch nodes comprising

a plurality of input conductors,

a plurality of output conductors,

storage means for variably storing a packet of said one of said messages and a plurality of address bits received from one of said input conductors,

means responsive to a predetermined number of said plurality of address bits from said one of said input conductors and a packet communication available signal from one of said output conductors defined by said predetermined number of address bits for immediately routing said received packet of said one of said messages to said one of said output conductors, and

means for repositioning said predetermined number of address bits in said plurality of address bits in the routing of said received packet to said defined one of said output conductors.

44. The invention of claim 43 wherein said switching system further comprising a plurality of distributed controllers each for interfacingly connecting an individual one of said transmission links to one of said packet switch nodes.

45. A method of communicating packets through a packet switching system comprising switching networks interconnected by a plurality of high speed digital transmission means with each transmission means being connected to a given network by one of a plurality of interface facilities, first type packets comprising logical addresses are transmitted via said transmission means at first predetermined data rate and second type packets comprising network addresses are transmitted within said networks at a second predetermined data rate greater than said first predetermined data rate, each of said switching network comprising switching elements responsive to the network addresses of said second type packets to route said second type packets to destination ones of said interface facilities, said method comprising the steps:

storing a one of said first type packets upon a receipt of said one of said first type packets by one of said interface facilities from associated transmission means;

translating the logical address contained in said one of said first type packets to the corresponding network address and another logical address in response to the storage of said one of said first type packets;

replacing said logical address with said other logical address in said one of said first type packets;

assembling one of said second type packets by concatenating said network address and said one of said first type packets; and

transmitting at said second predetermined data rate said one of said second type packets to said destination interface facility via said network.

46. A method of switching packets through a packet switching network comprising a first and a second stage with each stage being comprised of switching elements, each switching element having a plurality of input and output terminals, each of said switching elements of said first stage has an individual one of said output terminals connected to each of said switching elements of said second stage via the input terminals of said switching elements of said second stage, each switching element of said first and second stages having a variable storage means for buffering packets, said switching elements are responsive to an address contained within packets to route the packets from the input terminals to the address designated output terminals, and comprises the steps of

variably storing the first portion of a packet received on the input terminal of one of said switching elements of said first stage;

decoding said address field of said packet;

rearranging said address for decoding by a sequential one of said switching elements;

transmitting upon receipt of a link open signal said portion of said packet to the connected input terminal of a switching element of said second stage via the output terminal of said one of said switching elements of said first stage designated by said address field of said packet; and

transmitting said link open signal upon the storage means associated with said connected input terminal having capability of partially receiving said packet from said switching element of said first stage.