At&t Bell Laboratories

Bell Telephone Laboratories

American Telephone & Telegraph Co., At&t Bell Laboratories

Wing N Toy

Mikiel L Larson

Avinash K Vaidya

Kari T Teraslinna

Walter T Hartwell

Maurice N Ransom

Benjamin Zee

David L Hinshaw

Charles W Hoffner, Ii

Shih-jeh Chang

Lee E Gallaher

Liane C Toy

Anne A Robrock

A packet switching arrangement for receiving packets including broadcast addresses and connecting representations of the received packets to any combination of output ports specified in the address is disclosed. The packet routing units of the network both generate packet representations and selectively connect the representations to downstream routing units or network outputs. Packets for use with the network comprise an address portion encoded in a broadcast format or in a shorter point-to-point format and an address type character identifying the type of address in the address portion. The nodes of the network respond to the address type character of a received packet by selecting the appropriate decoding format for the packet address portion. A packet select unit decodes the address portion in accordance with the selected decoding format and selectively connects the packet to the network outputs.

Packet switching network for multiple packet types

A packet switching arrangement for receiving packets including broadcast addresses and connecting representations of the received packets to any combination of output ports specified in the address is disclosed. The packet routing units of the network both generate packet representations and selectively connect the representations to downstream routing units or network outputs. Packets for use with the network comprise an address portion encoded in a broadcast format or in a shorter point-to-point format and an address type character identifying the type of address in the address portion. The nodes of the network respond to the address type character of a received packet. By selecting the appropriate decoding format for the packet address portion, a packet select unit decodes the address portion in accordance with the selected encoding format and selectively connects the packet to the network outputs.

Broadcast packet switch network

An improved call waiting arrangement where a caller is free to exercise discretion in interrupting ongoing telephone calls because the caller is prompted, for example via an audible announcement, that the called party is busy on another call but that the caller may request interruption of the call by remaining off-hook. If the caller believes that his call is sufficiently important, he requests call interruption by remaining off-hook. If the caller chooses not to interrupt, he may make subsequent call attempts promptly because he knows that the called party is busy on another call rather than being away from home. Alternatively, the caller may activate auto-callback such that a call is completed between the two parties as soon as the status of the called station returns to on-hook.

Call waiting arrangement providing options to both a subsequent calling

A communication method and packet switching network in which self-routing packets are communicated to a single-destination port of the switching network, a plurality of grouped destination ports or to two distinct destination ports after the modification by the switching network of the self-contained routing information within the packets. The packet switching network has a plurality of stages with each stage comprising a plurality of switch nodes, and the communicated packets can be of the single-destination, broadcast, or multiple-destination types of packets. The routing information within the packet comprises pairs of data bits with each pair associated with a stage of the switching network and with the value of the pair of bits determines the type of packet for the corresponding stage. Each switching node has two input and two output terminals, and a switch node in a particular stage is responsive to a single-destination packet received on an input terminal to communicate the packet to the output terminal designated by the value of the pair of bits for that stage. A switch node is responsive to a broadcast type packet to communicate the packet to both output terminals. In response to a split-destination packet, a switch node examines the next pair of bits of the routing information relative to the pair corresponding to the switch node in order to form two new single-destination packets from the split-destination packet. The routing information of the split-destination packet is only modified with respect to this next pair of bits.

Packet switching network with multiple packet destinations

Trunk controllers (131) at each end of a trunk (118) of a packet switching system (FIGS. 1A and 1B) include an idle packet generator (1419) and an idle packet detector (1420). During idle periods, when packets are not available for transmission, the transmitter of each idle trunk controller generates and transmits a continuous sequence of flags (801/810) on the trunk. Periodically during the idle periods, the idle packet generator generates and provides to the transmitter (1403) for transmission an idle packet (800). An idle packet is structured like a normal packet. However, it is marked as an idle packet by the packet identification (PID) field (804) and contains pseudo-random bits in the data field (806). The receiver (1402) of the other trunk controller receives the idle code and packets including idle packets, discards the idle code, and sends all packets to the idle packet detector. The detector identifies idle packets by their PID field and discards them--blocks them from propagating further--while allowing other packets to pass therethrough.

Idle period signalling in a packet switching system

A self-routing packet switching network in which packets are communicated through stages of the network in response to self-contained addresses and in which a packet is discarded if a packet cannot be transferred to a subsequent stage of the network within a predefined amount of time. In addition, upon a packet being discarded, a maintenance message is transmitted over a maintenance channel to the processor controlling the network. Each network comprises stages of switching nodes which are responsive to the physical address in a packet to communicate the packet to a designated subsequent node. The nodes provide for variable packet buffering, packet address rotation techniques, and inter-node and intra-node signaling protocols. Each node comprises a timer which commences timing for a predefined amount of time upon receipt of a packet. If the timer times out, the packet is discarded and a maintenance message is transmitted to the processor controlling the network. The maintenance message includes the physical address plus an address identifying the network entry point of the packet. By discarding packets after a predefined amount of time, the problem of a self-routing network locking up is avoided when one switching node within the network fails or is experiencing overload traffic conditions.

Lockup detection and recovery in a packet switching network

A communication method and packet switching network in which self-routing packets are communicated via multipaths through the network while maintaining the sequence of the packets. The switching network has a plurality of stages and the stages are interconnected by inter-node links. Each inter-node link comprises a pair of sublinks thus establishing multipaths through the switching network in response to the self-routing packets. Each stage has a plurality of switch nodes. A switch node is responsive to packets received on one inter-node like destined for a second inter-node link to maintain the sequence of packets as they are communicated out on the second inter-node link. Each node comprises a plurality of input circuits each individually connected to one of the incoming sublinks and a plurality of output circuits each connected to one of the outgoing inter-node links. Each output circuit has an arbiter which properly sequences the packets onto the outgoing link in response to requests for communicating packets received from the input circuits.

Self-routing multipath packet switching network with sequential delivery

A traffic load control arrangement for a packet switching system (FIGS. 1A and 1B) uses a circuit (1521) in each trunk controller (131) to determine the call traffic load of the trunk controller. To set up a call path, the central processor (115) of a switch (102) selects a trunk (118) to serve the call and sends a logical channel setup packet (500e) indicating either forced or normal selection to the selected trunk's controller (131). If normal selection is indicated, the selected trunk controller refuses to serve the call and returns a channel setup no-acknowledgement packet (500f) to the central processor if the trunk controller's load exceeds a predetermined level. Otherwise, the trunk controller sets up a channel to serve the call and returns a channel setup acknowledgment packet (500g) to the central processor. In response to the no-acknowledgment packet, the central processor attempts to find another trunk to serve the call. In the case of a toll office (104), if no other trunk can be found and a call setup acknowledgment packet (500n) has not yet been returned by the toll office switch to the preceding switch, the toll office switch returns a call setup no-acknowledgment packet (500o) to the preceding switch. The preceding switch responds to receipt of the no-acknowledgment packet by attempting to find a trunk leading to another switch to serve the call.

Traffic load control arrangement and method for a packet switching system

A packet switching network (100) comprises switching nodes (220-222, 230-232, 240-242, 250-252, 260-262, and 270-272) residing on circuit packs (101-104), that are interconnected by packet signal transmission links (110-119, 140-149, 150-159, and 180-189) carrying multiplexed pulse-width modulated signals (450) each representing three bits. A link (112) incoming to a pack (101) connects to an input port (2821) of a demultiplexer (282), whose output ports (2822-2824) are coupled to packet inputs (2401, 2411, 2421) of three nodes (240-242). The incoming signal stream is demultiplexed into three serial signal substreams. Each substream is transmitted to a node for switching. A link (122) outgoing from a pack (101) connects to an output port (2871) of a multiplexer (287) whose input ports (2872-2874) are coupled to the packet outputs (2703, 2713, 2723) of three nodes (270-272). The three incoming serial signal substreams are multiplexed into a signal stream that is transmitted on the link. For multiplexed signals representing the bits of a single packet, (FIGS. 2a-c), the acknowledgment output (2405) of one node (240) coupled to a demultiplexer (282) is connected to the incoming link (112) and the acknowledgment input (2707, 2717, 2727) of each node (270-272) coupled to a multiplexer (287) is connected directly to the outgoing link (122). For multiplexed signals representing the bits of three packets, (FIGS. 3a-c), acknowledgment outputs (2405, 2415, 2425) of the nodes (240-242) that are coupled to a demultiplexer (282) are coupled through a multiplexer (294) to the incoming link (112). Acknowledgment inputs (2707, 2717, 2727) of the nodes (270-272) that are coupled to a multiplexer (287) are coupled through a demultiplexer (291) to the outgoing link (122). Coupling of a packet and acknowledgment input and output pair to a demultiplexer and a multiplexer is made by a lock (246) which alternately makes one connection while it breaks the other connection. The locks that connect to a multiplexer and demultiplexer pair operate in unison.

Multiplexed interconnection of packet switching node packages

A cache memory system reduces cache interference during direct memory access block write operations to main memory. A control memory within cache contains in a single location validity bits for each word in a memory block. In response to the first word transferred at the beginning of a direct memory access block write operation to main memory, all validity bits for the block are reset in a single cache cycle. Cache is thereafter free to be read by the central processor during the time that the remaining words of the block are written without the need for additional cache invalidation memory cycles.

Cache arrangement for direct memory access block transfer

In a computer system having a cache memory and using virtual addressing, effectiveness of the cache is improved by storing a subset of the least significant real address bits obtained by translation of a previous virtual address and by using this subset in subsequent cache addressing operations. The system functions in the following manner. In order to access a memory location in either the main memory or cache memory, a processor generates and transmits virtual address bits to the memories. The virtual address bits comprise segment, page and word address bits. The word address bits do not have to be translated, but an address translation buffer (ATB) translates the segment and page address into real address bits. A subset of the least significant bits of the latter word address bits represent the address needed for accessing the cache. In order to increase cache memory performance, the cache memory comprises a cache address unit which stores the subset of the real address bits from the ATB. These stored address bits are used in subsequent operations along with the word address bits for accessing the cache memory until the stored address bits no longer equal the current subset of least significant real address bits transmitted from the ATB. When the stored address bits no longer equal the current subset, the cache address unit then stores the current subset; and the cache memory is reaccessed utilizing the word address bits and current subset.

Cache addressing arrangement in a computer system

The processor's interrupt stack memory and cache memory share a common data memory and are accessed using virtual addresses. A separate address translation buffer (ATB) is used for both the interrupt stack memory and cache memory to perform the virtual address to real address translations which are required to access the common data memory. The cache ATB and a cache controller provide the addressing to access cache data words in the common memory; whereas the interrupt stack ATB alone provides the addressing necessary to access the interrupt stack data words in the common memory.

Computer with dual vat buffers for accessing a common memory shared by a

A circuit for the detection of errors in single and double word arithmetic logic unit operations. A microprogram processor achieves self-checking of arithmetic logic unit functions by performing single-word operations in the duplex mode and double-word operations in the simplex mode. The double-word operation is checked by performing the operation twice, generating a parity bit for each output word and comparing the parity bits generated for the two operations.

Self-checking arithmetic unit

A data processing system includes a memory arrangement comprising a main memory, and a cache memory including a validity bit per storage location to indicate the validity of data stored therein. Cache performance is improved by a special read operation to eliminate storage of data otherwise purged by a replacement scheme. A special read removes cache data after it is read and does not write data read from the main memory into the cache. Additional operations include: normal read, where data is read from the cache memory if available, or, from main memory and written into cache; normal write, where data is written into main memory and the cache is interrogated, in the event of a hit, the data is either updated or effectively removed from the cache by invalidating its associated validity bit; and special write, where data is written both into main memory and the cache.

Data processing system including a cache memory

A word organized random access memory comprises a plurality of circuit packs arranged such that the memory capacity can be easily increased or decreased in increments corresponding to the word capacity of a single circuit pack while distributing the power dissipation associated with accessing a word across a plurality of the circuit packs. Each circuit pack comprises two or more independently accessible memory modules with each module arranged to store a plurality of word segments each of which comprises corresponding segments of different memory words. Input, output, and control wiring is provided such that access control of the circuit packs associates the packs into a chain which is looped back on itself. Links of this chain comprise groups of modules which define memory word locations wherein no two modules of a group are packaged on the same circuit pack. Loop around connections complete groups by interconnecting incomplete groups from the end of the chain with complementary incomplete groups from the beginning of the chain. The capacity of the memory is increased or decreased by adding or deleting one or more circuit packs in the chain. Switches are provided to accommodate the insertion or deletion of a circuit pack.

Growing community of inventors

Glen Ellyn, IL, United States of America

Wing N Toy