Broadcast packet switching network

• US 4,734,907 A
• Filed: 09/06/1985
• Issued: 03/29/1988
• Est. Priority Date: 09/06/1985
• Status: Expired due to Fees

• Current Assignee: Washington University In St Louis
• Original Assignee: Washington University In St Louis
• Inventors: Turner, Jonathan S.
• Primary Examiner(s): Olms, Douglas W.
• Application Number:
  US06/773,380
• Time in Patent Office: 935 Days
• Field of Search: 370/94, 370/60, 370/89, 340/825.5
• US Class Current: 370/390
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
• CPC Class Codes: H04L 49/106 using space switching, e.g. crossbar or matrix
• CPC Class Codes: H04L 49/1507 Distribute and route fabrics, e.g. sorting-routing or Batcher-Banyan
• CPC Class Codes: H04L 49/1561 Distribute and route fabrics, e.g. Batcher-Banyan
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/253 using establishment or release of connections between ports
• 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/357 Fibre channel switches
• CPC Class Codes: H04L 49/505 Corrective measures
• CPC Class Codes: H04L 49/557 Error correction, e.g. fault recovery or fault tolerance

Abstract

A high performance packet switching network that can be used to provide voice data and video communication on a large scale is disclosed. The packet switching network has a broadcast capability which makes it suitable for applications including commercial television distribution and conferencing.

The basic switching capability of the network is provided by a switching module which is capable of producing a desired number of copies of a broadcast packet and routing the copied packets to desired destinations. A plurality of switching modules may be interconnected to form a packet switch. Interconnection circuitry is provided so that the number of interconnected switch modules may be varied with a minimum of recabling.

Claims

1. A packet switch comprising

copy network means for receiving information packets at individual inputs thereof and replicating identical copies at multiple outlets thereof,

routing and distribution network means for receiving packets from said copy network means and transmitting them to predetermined destinations, and

control means responsive to information contained in the packets for determining the number of copies to be replicated by said copy means and said destinations.

2. A packet switch in accordance with claim 1 wherein said routing and distribution network means includes a routing network for routing packets to said destinations and a distinct distribution network for evenly distributing packets from said copy network means to said distribution network.

3. A packet switch in accordance with claim 2 wherein said control means includes translator means between said copy network means and said distribution network for providing each of said packet copies leaving said copy network with a destination address.

4. A packet switch in accordance with claim 2 wherein said control means includes first and second translation means between said copy network means and said distribution network,

said first translator means providing at least some of said packet copies leaving said copy network with an identification number for a group of destinations, and

said second translator means providing to those packets with an identification number provided by said first translator means the address of one of said destinations in the group identified by said number in a manner so that all destinations in a group receive approximately the same volume of packet traffic.

5. A switch module for use in a packet switching network having broadcast capability comprising:

6. a copy network having a plurality of inputs and a plurality of outputs, said copy network being capable of receiving data packets at said inputs and replicating said packets to produce copies of said packets at said outputs,

7. memory means in communication with the outputs of said copy network for providing destination address information for each of the packet copies produced by said copy network, and

8. a routing network capable of routing each of the packet copies to a desired destination having an address supplied by said memory means.

9. A switch module for use in a packet switching network, said switch module terminating a plurality of bidirectional data links and being capable of routing point-topoint packets from one of said data links to another of said data links and being capable of copying broadcast packets and routing broadcast packets to a pluralty of said links, said switch module comprising

a copy network comprising a plurality of nodes arranged in stages and having a plurality of inputs and a plurality of outputs, said copy network being capable of passing unchanged each point-to-point packet from one of said inputs to one of said outputs, and replicating each broadcast packet to produce copies at at least some of said outputs,

memory means coupled to said copy network outputs for supplying an address of an outgoing data link to each copy of a broadcast packet leaving said copy network, and

a routing network for routing said point-to-point packets and said broadcast packets to outgoing data links.

13. The switch module of claim 9 wherein each packet arriving at a given one of said processors by way of an associated data link includes a logical channel number for indexing the translation memory means in said given processor, said translation memory means serving to cause routing information to be written into each packet indicating whether each packet is a point-to-point packet or a broadcast packet.

17. The packet switch module of claim 13 wherein a particular copy bound for a particular destination may exit the copy network at any of a group of said outputs of said copy network, and wherein said first memory means associated with each of said outputs in said group is capable of providing said particular packet with the address of said particular destination, whereby said particular packet is routed to said particular destination regardless of which output in said group said particular packet uses.

10. A switch module for use in a packet switching network, said switch module terminating a plurality of bidirectional data links and being capable of routing point-topoint packets from one of said data links to another of said data links and being capable of copying packets and routing broadcast packets to a plurality of said links, said switch module comprising

a copy network for passing each point-to-point packet unchanged and for making a desired number of copies of each broadcast packet,

memory means for supplying an address of an outgoing data link to each copy of a broadcast packet leaving said copy network, and

a routing network for routing said point-to-point packets and said broadcast packets to outgoing data links,

said switch module further comprising a distribution network for preventing congestion in said routing network interposed between said copy network and said routing network.

14. The switch module of claim 10 wherein said packet is a point-to-point packet and said information includes the address of the data link over which said packet leaves said switch module.

15. The switch module of claim 10 wherein said packet is a broadcast packet and said information includes the number of copies to be made by the copy network and a broadcast channel number for determining a destination address for each packet copy made by said copy network.

19. The method of claim 15 wherein said providing step comprises the steps of indexing a memory utilizing an identification number contained in said packet and writing into said packet the address of a destination data link.

20. The method of claim 15 wherein said providing step comprises the steps of indexing a first memory and writing into each packet copy an identification number for a group of data links and indexing a second memory with said indentification number and writing into said packet the address of one of said data links in said group, the address of said one data link being chosen so that all of the data links in said group receive approximately the same volume of packet traffic.

11. A switch module for use in a packet switching network, said switch module terminating a plurality of bidirectional data links and being capable of routing point-to-point packets from one of said data links to another of said data links and being capable of copying broadcast packets and routing broadcast packets to a plurality of said links, said switch module comprising

a copy network for passing each point-to-point packet unchanged and for making a desired number of copies of each broadcast packet,

memory means for supplying an address of an outgoing data link to each copy of a broadcast packet leaving said copy network, and

a routing network for routing said point-to-point packets and said broadcast packets to outgoing data links,

wherein some of said point-to-point packets include a number identifying a group of outgoing data links and wherein said switch module includes further memory means for translating said group identification number into the address of one of said links in said group in a manner so that all links in said group receive approximately the same volume of packet traffic.

12. A switch module for use in a packet switching network, said switch module terminating a plurality of bidirectional data links and being capable of routing point-to-point packets from one of said data links to another of said data links and being capable of copying broadcast packets and routing broadcast packets to a plurality of said links, said switch module comprising

a copy network for passing each point-to-point packet unchanged and for making a desired number of copies of each broadcast packet,

memory means for supplying an address of an outgoing data link to each copy of a broadcast packet leaving said copy network, and

a routing network for routing said point-to-point packets and said broadcast packets to outgoing data links,

wherein said copy network has a plurality of inputs and said routing network has a plurality of outputs and wherein said switch module further comprises a plurality of processors, each of said processors interfacing one of said bidirectional links with one input of said copy network and one output of said routing network, each of said processors comprising translation memory for supplying routing information to packets for routing said packets through said switch module.

16. A packet switch module comprising

copy network means for receiving broadcast packets at individual inputs thereof and replicating identical copies at multiple outputs thereof,

first memory means associated with each output of said copy network for providing each of said copies leaving said copy network with routing information to enable each of said copies to be routed to a destination;

second memory means associated with each of said first memory means for controlling the writing of said routing information into each of said first memory means, each of said second memory means capable of being indexed by a broadcast destination update packet containing a plurality of routing information entries to retrieve information which identifies which of said routing information entries in said broadcast destination update packet is to be written into the associated first memory.

18. A method for copying a data packet and distributing the copies of the data packet to a plurality of destinations comprising the steps of

receiving said packet at an input of a copy network and replicating said packet in said copy network so that a plurality of copies of said packet emerge at a plurality of outputs of said copy network,

providing each of said packet copies emerging at the outputs of said copy network with a destination address by indexing a memory, and

routing each of said packet copies through a routing network to its destination.

22. The process of claim 18 comprising a further step of randomly routing each packet to one of said output ports when the number of remaining copies to be made is less than 2^sn-1.

21. A process of controlling the passage of data packets through a binary network comprising a plurality of switching elements arranged in stages, each said element having a pair of inputs and a pair of outputs and wherein each packet has an NC field to indicate the number of remaining copies to be made of the packet during the passage of the packet through the network comprising the steps of:

(a) ascertaining for each entering packet the number of copies of the incoming packet which are to be made for broadcast to a plurality of destinations,

(b) controlling the element of the stage receiving said packet to deliver said packet to each output of said pair when the number of remaining copies to be made exceeds 2^sn-1 where sn identifies the position of the said last-mentioned stage relative to the position of the output stage in said network, and

(c) when the broadcast channel number of the packet is even, changing the number recorded in said NC field in said packet at the uppermost one of said pair of outputs to the integer part of (NC+1)/2 and changing the number recorded in said NC field in said packet at the lowermost one of said pair of outputs to the integer part of NC/2, and

(d) when the broadcast packet number is odd, changing the NC field of said upper packet to the integer part of NC/2 and the integer part of said lower packet to the integer part of (NC+1)/2.