Chiaro Networks Ltd

Hewlett-packard Development Company, L.P.

Hewlett-packard Company

Foundry Networks, Inc.

Jeremy Benjamin As Receiver for Chiaro Networks Ltd.

Gregory S Palmer

Tony M Brewer

Keith W Shaw

Jim Kleiner

Bryan D Hornung

Paul F Vogel

Harold Wallace Dozier

Thomas C McDermott, Iii

Harry C Blackmon

David Traylor

Dean E Walker

Michael L Ziegler

Michael K Dugan

Michael K Traynor

Instead of alternatively utilizing only one fabric or the other fabric of a redundant pair, both fabrics simultaneously transmit duplicate information, such that each packet forwarding module (PFM) receives the output of both fabrics simultaneously. In real time, an internal optics module (IOM) analyzes each information chunk coming out of a working zero switch fabric; simultaneously examines a parallel output of a working one duplicate switch fabric; and compares on a chunk-by-chunk basis the validity of each and every chunk from both switch fabrics. The IOM does this by examining forward error correction (FEC) check symbols encapsulated into each chunk. FEC check symbols allow correcting a predetermined number of bit errors within a chunk. If the chunk cannot be corrected, then the IOM provides indication to all PFMs downstream that the chunk is defective. Under such conditions, the PFMs select a chunk from the non-defective switch fabric. Under error-free normal conditions, however, the PFMs select a chunk arbitrarily from a default switch fabric. In this way, each chunk in real time is selected from a non-defective source and is thus guaranteed to be error free. Accordingly, if a switch fabric fails, no information chunks are lost anywhere in the system.

Router switch fabric protection using forward error correction

In a multi-QOS level queuing structure, packet payload pointers are stored in multiple queues and packet payloads in a common memory pool. Algorithms control the drop probability of packets entering the queuing structure. Instantaneous drop probabilities are obtained by comparing measured instantaneous queue size with calculated minimum and maximum queue sizes. Non-utilized common memory space is allocated simultaneously to all queues. Time averaged drop probabilities follow a traditional Weighted Random Early Discard mechanism. Algorithms are adapted to a multi-level QOS structure, floating point format, and hardware implementation. Packet flow from a router egress queuing structure into a single egress port tributary is controlled by an arbitration algorithm using a rate metering mechanism. The queuing structure is replicated for each egress tributary in the router system.

System and method for router queue and congestion management

A router line card is partitioned to separate the packet forwarding functions from physical port interfacing. For each packet forwarding card, at least one redundant port interface is provided. Identical input packets are transmitted via these redundant input port interfaces, one of which is eventually selected based on, for example, SONET standard criteria. If there is a failure, the router selects the interface path that is operating properly and rejects the path containing a failed element. Thus, the router decides locally how to correct the problem internally. Moreover, following an equipment failure the now offline failed interface path can be replaced, while the equipment remains in service using the duplicated interface path. The system can be restored to full duplex operation without affecting the existing traffic, providing for a hot replacement of a failed path. Because the interfaces are separate, a failed module can be renewed and replaced while the equipment is in service. If a failure occurs in an interface card between two peer routers, then packets flow between the two routers uninterrupted from exactly the same previous ports on one router to the same previous ports on the second router, using the same Internet protocol addresses as existed prior to the switching.

Router network protection using multiple facility interfaces

The present invention implements a mechanism for reliably communicating transaction messages between source and destination devices connected across an unreliable network, where a transaction is an operation requested by a source device of a destination device and where a plurality of messages are exchanged between source and destination in order to ensure completion of the transaction. Because the network linking the source and destination is unreliable, the source and destination operate to preserve data regarding the transaction messages which they have received and transmitted. If responsive messages are not timely received, they are generally resent. A dual timing system is preferably implemented to ensure that there are never two identical messages simultaneously in transmission through the network.

Protocol for insuring exactly once semantics of transactions across an unordered, unreliable network

A centralized arbitration mechanism provides that a router switch fabric is configured in a consistent fashion. Remotely distributed packet forwarding modules determine which data chunks are ready to go through the optical switch and communicates this to the central arbiter. Each packet forwarding module has an ingress ASIC containing packet headers in roughly four thousand virtual output queues. Algorithms choose at most two chunk requests per chunk period to be sent to the arbiter, which queues up to roughly 24 requests per output port. Requests are sent through a Banyan network, which models the switch fabric and scales on the order of NlogN, where N is the number of router output ports. Therefore a crossbar switch function can be modeled up to the 320 output ports physically in the system, and yet have the central arbiter scale with the number of ports in a much less demanding way. An algorithm grants at most two requests per port in each chunk period and returns the grants to the ingress ASIC. Also for each chunk period the central arbiter communicates the corresponding switch configuration control information to the switch fabric.

System and method for router central arbitration

A system for moving checksums within memory utilizes a plurality of memory systems and a system manager. A first memory system has a first memory location that is correlated with a checksum indicator. The checksum indicator identifies the memory system that is storing the checksum of the value presently stored at the first location. The system manager dynamically moves the checksum to a destination memory location and updates the checksum indicator such that the checksum indicator identifies the memory system of the destination memory location. While the checksum is being moved, checksum updates may occur to the memory location from which the checksum was moved. Thus, after moving the checksum, the system manager updates the checksum with the value stored at the location from which the checksum was moved. As a result, the checksum stored in the checksum destination location should be sufficiently updated to enable data recovery.

System and method for dynamically moving checksums to different memory locations

In a router with redundant central arbiters, a set of control processors (CPs) determines which arbiter is active, which is standby, and when to switch between them. In normal operation ingress ASICs issue requests to the active central arbiter ASIC and keep-alive requests cyclically once per chunk period to the passive arbiter ASIC, which then returns keep-alive grants through the same links to the ingress ASICs and sends standby configuration information to the optical switch ASICs. The arbiter ASICs pass a switch-over decision simultaneously to the optical switch ASICs and ingress ASICs, which empty all queues of outstanding requests, and then resend all of those requests to the new active central arbiter after all queues are empty, such that no router traffic is lost. Mechanisms ensure that during the transition the ASICs properly recognize which data links are healthy and which arbiter is active.

System and method for router arbiter protection switching

Router line cards are partitioned, separating packet forwarding from external or internal interfaces and enabling multiple line cards to access any set of external or internal data paths. Any failed working line card can be switchably replaced by another line card. In particular, a serial bus structure on the interface side interconnects any interface port within a protection group with a protect line card for that group. Incremental capacity allows the protect line card to perform packet forward functions. Logical mapping of line card addressing and identification provides locally managed protection switching of a line card that is transparent to other router line cards and to all peer routers. One-for-N protection ratios, where N is some integer greater than two, can be achieved economically, yet provide sufficient capacity with acceptable protection switch time under 100 milliseconds. Alternatively, protect line cards can routinely carry low priority traffic that is interruptible, allowing the protect line card to handle higher priority traffic previously carried by a failed working line card. This approach renders unnecessary engineering a network for less than full capacity to allow rerouting in the event of individual line card failure. Consequently, all data paths can be fully utilized. If a particular interface module on one data bus needs removal for maintenance, a duplicate data bus is available intact, allowing hot replacement of any working or protect interface module, even while a line card protection switch is in effect.

Router line card protection using one-for-N redundancy

Hardware interconnected around multiple packet forwarding engines prepends sequence numbers to packets going into multiple forwarding engines through parallel paths, After processing by the multiple forwarding engines, packets are reordered using queues and a packet ordering mechanism, such that the sequence numbers are put back into their original prepended order. Exception packets flowing through the forwarding engines do not follow a conventional fast path, but are processed off-line and emerge from the forwarding engines out of order relative to fast path packets. These exception packets are marked, such that after they exit the forwarding engines, they are ordered among themselves independent of conventional fast path packets. Viewed externally, all exception packets are ordered across all multiple forwarding engines independent of the fast path packets.

System and method for router packet control and ordering

A system for building checksums efficiently builds a checksum of various data values that are stored in different memory units of a computer system. During the checksum build process, data stores to the memory locations storing the various data values are enabled, thereby enabling the checksum to be built without significantly impacting the performance of the computer system.

System and method for building a checksum

In general, a system and method is provided for dynamically reallocating computer memory. A mapper receives requests to access data. The requests include bus addresses, and the mapper maps the bus addresses to memory unit addresses based on a plurality of mappings maintained by the mapper. The memory unit addresses identify a plurality of memory locations including a destination memory location and a source memory location. Data requested by the requests received by the mapper is accessed based on the memory unit addresses mapped from the bus addresses included in the requests. When desired, a data value from the source memory location is dynamically moved to the destination memory location, and the mappings are updated such that a bus address mapped to a memory unit address identifying the source memory location is instead mapped to a memory unit address identifying the destination memory location.

Growing community of inventors

Plano, TX, United States of America

Gregory S Palmer