Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-12-04
2003-06-24
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000, C370S462000, C709S238000
Reexamination Certificate
active
06584101
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of data transmission, and in particular to a method of routing data messages in a digital switching network.
BACKGROUND TO THE INVENTION
Data switching networks are generally configured with data transceivers (nodes) connected in ring structures or in star structures. As is well known, in the ring structure, for example, data signals are transmitted around the ring, with each transceiver detecting whether its address is at the head of a frame. If so, it accepts the frame of data. In star networks, there is a central switching system through which each message passes, which detects the addresses and routes the messages to the particular arm of the star to which the addressed node is connected.
Well known switching networks conform to the FDDI, FC and SCI standards, and fall into two general classes:
1. Output buffered architectures which associate data storage with the transmit side of a port of a node. This structure simplifies input ports since data can be sent directly from the receive port of the node to its output port without scheduling or storage. However, the switching fabric of the network which interconnects ports must have excess bandwidth approaching twice the port bandwidth per attached port. In addition, the output port must have all the scheduling, storage and ordering capabilities of the switch since there is no other inherent way in the node to control traffic destined for the output port.
2. Input buffered switches which store data immediately on the receive side of the port. This eliminates the complexities of the output buffered switch with respect to speed and overlay traffic control. Data can be stored independently of the state of the other ports or the state of the interconnecting switching mechanism. However, for this type of switch, the state of the output port must be known before the data can be sent through the switching interconnection.
In the input buffered switch type of switching structure, the output port state has been obtained by an out of band scheduling mechanism, or by using a reservation protocol. Reservation protocols require the synchronization of distributed state machines with arbitrary loads and timings. Centralizing the scheduling eliminates the advantages of the protocol approach while still requiring the protocol elements. However, distributed schedulers would require buffering on both input and output ports that would greatly increase the cost of the switch.
Whether distributed or centralized, out of band scheduling cannot be scaled in number of nodes, and therefore is inflexible. Reservation protocols have provided the most flexible solution but involve complex scheduling and distributed arbitration.
SUMMARY OF THE INVENTION
The present invention is comprised of embodiments which can provide a distributed switch that could be easily expanded across multiple interconnection fabrics and an arbitrary number of nodes. It uses an embedded protocol which is used for distributed scheduling, as distinct from resource reservation. This eliminates the requirement for arbitration among shared resources and requires only physical link feedback and arrival time state information to be processed at the egress port of the node.
The present invention provides scalability, low cost, distributed pipeline scheduling, a single point of data buffering, no external arbiters or schedulers, and allows maximum complexity of the network fabric and maximum speed. To obtain these advantages, the present invention has a stateless, distributed control messaging structure, associates outputs within an input only buffered memory, utilizes a unidirectional point-to-point electrical network interconnection structure, and eliminates any centralized devices while maintaining seamless growth via an unidirectional handshaking protocol.
In accordance with an embodiment of the invention, a method of communicating frames of data in a network comprised of nodes, each node having an unidirectional ingress port and an unidirectional egress port, comprises transmitting messages from the egress port of a source node to the ingress port of a destination address, determining whether an address in the message represents the destination node and if so absorbing the message, and if not buffering the message as bypass data prior to transmission out of the egress port of the destination node to an ingress port of a downstream node.
In accordance with another embodiment, a method of communicating in a network comprised of one or more end system (ES) nodes, each ES node having a unidirectional ingress and a unidirectional egress port, wherein an egress port of one ES node is coupled to the ingress port of itself or of another ES node and wherein a message frame transmitted from the egress port of any ES node can reach the ingress port of an ES node of the network, comprises:
(a) from a source ES node egress port which has a message frame to be transmitted to an ingress port of itself or of another destination ES node, transmitting a queue allocation request,
(b) allocating a buffer having a predetermined data block size in the destination ES node, and transmitting a queue fetch request from the destination ES node to the source ES node,
(c) receiving the queue fetch request at the first ES node and in response transmitting the predetermined data block of the message frame from the source ES node to the destination ES node, and
(d) detecting a destination address in the message frame at the destination ES node and either routing the message to the local resource or to its egress port for retransmission to another ES node.
REFERENCES:
patent: 4486739 (1984-12-01), Franaszek et al.
patent: 4748658 (1988-05-01), Gopal et al.
patent: 5014221 (1991-05-01), Mogul
patent: 5361372 (1994-11-01), Rege et al.
patent: 5509061 (1996-04-01), Amereller et al.
patent: 5640495 (1997-06-01), Colbert et al.
patent: 5765023 (1998-06-01), Leger et al.
patent: 5781799 (1998-07-01), Leger et al.
patent: 5878217 (1999-03-01), Cherukuri
patent: 5978876 (1999-11-01), Greaves
patent: 5982994 (1999-11-01), Mori et al.
patent: 6028837 (2000-02-01), Miller
patent: 6075615 (2000-06-01), Nakamura
patent: 6081522 (2000-06-01), Hendel et al.
patent: 6213652 (2001-04-01), Suzuki et al.
IEEE Std. 1596.3-1996—IEEE Standard for Low-Voltage Differential Signals (LVDS) for Scalable Coherent Interface (SCI), Jul. 31, 1996.
IEEE Std. 1596.5-1993—IEEE Standard for Shared-Data Formats Optimized for Scalable Coherent Interface (SCI) Processors, Apr. 25, 1994.
IEEE Std 1596-1992—IEEE Standard for Scalable Coherent Interface (SCI) May 23, 2001.
ANSI NCITS 332-1999—Fiber Channel Arbitrated Loop (FC-AL-2).
ANSI X3.148-1998—Fiber Distributed Data Interface (FDDI)—Token Ring Physical Layer Protocol (PHY).
ANSI X3.166-1990—Fiber Data Distributed Interface (FDDI)—Toekn Ring Physical Layer Medium Dependent (PMD).
ANSI X3.139-1987—Fiber Distributed Data Interface (FDDI)—Token Ring Media Access Control (MAC).
ANSI X3.230-1994—Fiber Channel—Physical and Signaling Interface (FC-PH).
Adminission Control and Routing in ATM Networks Using Inferences from Measured Buffer Occupany, IEEE Trans. on Communications, Feb./Mar./Apr. 1995.
Architecutres for ATM Switching Systems, IEEE Communications Magazine, Feb., 1993.
Switching Fabrics with internal Backpressure Using the ATLAS I Single-Chip ATM Switch, IEEE Globecom'97 Conference, Nov. 1997.
ATLAS I: A General Purpose, Single-Chip ATM Switch with Credit-Based Flow Control, IEEE Hot Interconnects IV Symposium Proceedings, Aug., 1996.
A DC-Balanced, Partitioned-Block 8B/10B Transmission Code, IBM, Sep. 1983.
Performance of the SCI Ring, ACM Publication, 1992.
Pipelined Multi-Queue Management in a VLSI ATM Switch Chip with Credit-Based Flow-Control IEEE, 1997.
National Semiconductor QR0001 Quick Ring Data Stream Controller, Preliminary, Oct., 1994.
MIL-STD-2204—Survivable Adaptable Fiber Optic Embedded Network (SAFENET), May 4, 1998.
MIL-HDBK-818—Survivable Adaptable Fiber Optic Embedded Network (SAFENET) Network Development Guidance,
Alexander Thomas
Hagglund Barry Benjamin
Little Vernon Robert
Cohen Shapiro
Kizou Hassan
Pezzlo John
PMC-Sierra Ltd.
LandOfFree
Communication method for packet switching systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Communication method for packet switching systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Communication method for packet switching systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3097033