Lucent Technologies Inc.

Alcatel-lucent USA Inc.

Hong-Yi Tzeng

Kai-Yeung S Siu

Paolo Narvaez-Guarnieri

Murali Aravamudan

Shivendra S Panwar

Vijay Pochampalli Kumar

Dimitrios Stiliadis

Sunder Raj Rathnavelu

Yiwei Thomas Hou

Raman Arunachalam

Paolo Narvaez

Yin Zhang

A scalable, high-speed router for routing packets of information through an interconnected network comprises an interface for receiving a packet containing header and data information; a device for extracting routing information from the header of an arrived packet and generating a corresponding header packet for the arrived packet; a memory device for storing the data information of the arrived packet at predetermined memory locations; a device for processing the corresponding header packet to determine a route for the arrived packet and assigning packet forwarding information to the header packet; and, a device for retrieving the data information from the predetermined memory locations and forwarding both the data and header packet containing the packet forwarding information to the interface for routing the packet to a further destination in accordance with the packet forwarding information. The processing device includes devices performing filtering, route-table lookup and flow identification functions and which devices are organized in a pipelined fashion for successive, high-speed operations on the header packet. The router ensures that the arrived packet is forwarded in accordance with any quality of service requirements and flow specifications.

Scalable high speed router apparatus

This document describes a protocol for reliably synchronizing states of nodes in a distributed environment through use of a Scalable Atomic Multicast (SAM) Service that ensures both atomicity and total order among messages sent to a multicast group. In addition to possessing good scalability property, this fault-tolerant protocol does not require explicit knowledge of multicast group membership, allows for non-disturbing state synchronization, and supports asynchronous non-blocking communications. According to one aspect of this invention, a dedicated sequencer is responsible solely for assigning sequence numbers to the multicast messages. The sequencer does not multicast the messages. Another aspect of the invention is the use of receiver-driven negative acknowledgments. According to third aspect, the invention supports message consolidation and garbage collection.

Scalable atomic multicast

This invention is an algorithm that restores routing in a link-state network after a link failure without flooding the entire routing area with new routing information. The algorithm operates only in the local neighborhood of the failed link and informs the minimum number of routers about the failure.

Fault-tolerant non-flooding routing

A dynamic shortest path tree (SPT) algorithm for a router determines a new SPT for a root node in response to a link-state or other network topology change. The dynamic SPT algorithm determines the new SPT as an optimization problem in a linear programming framework based in an existing SPT in the router. The dynamic SPT algorithm emulates maximum decrement of a ball and string model by iteratively selecting nodes of the existing SPT for consideration and update of parent node, child nodes, and distance attributes based on the maximum decrement. For the maximum decrement, a node in the existing SPT is selected by each iteration based on the greatest potential decrease (or least increase) in its distance attribute. The ball and string model that may be employed for the dynamic SPT algorithm represents a network of nodes and links with a ball representing a node and a string representing a link or edge. The length of a string is defined by its link's weight. The set of strings connecting the balls defines a path between the root node and a particular node. The shortest path is the path defined by the strings from a root node to a particular node that are tight. For the dynamic SPT algorithm, an increase (or decrease) in an edge weight in an existing SPT corresponds to a lengthening (or shortening) of a string. By sequentially pulling balls away in a single direction from the ball of the root node, the new SPT becomes defined by the balls and tight strings.

Dynamic algorithm for determining a shortest path tree between network nodes

A packet network employs flow control providing assigned rates to sessions in accordance with a general max-min (GMM) rate allocation. The GMM rate allocation accounts for the minimum cell rate and peak cell rate requirements for each session. For one case, a centralized flow control algorithm is employed that sorts sessions based on increasing minimum cell rate. The centralized flow control algorithm employs an iterative process of increasing the rate of the smallest rate session and adding sessions to the process when the smallest rate session equals the next higher rate session. The rates are increased until the rate either reaches the peak cell rate of the session or the link saturates. For a second case, a distributed flow control algorithm is employed with a distributed protocol within the network to allocate capacity of network links to sessions. For the distributed flow control algorithm, an iterative process of rate allocation uses a modified version of the Consistent Marking method. In the modified version of the Consistent Marking method, a saturated link only marks those sessions reaching a corresponding GMM-bottleneck link rate on links elsewhere in the network. The session traversing its own GMM-bottleneck link is not marked.

Available bit rate flow control for service allocation in a packet network

A novel data structure in a router helps to compute viable next hops for forwarding a data packet from a router to its destination along multiple alternate loop-free paths, which are not necessarily of shortest distance. Each viable next hop may also be specified with a degree of optimality, which enables a route to perform QoS routing and fault-tolerant routing efficiently. The data structure can be implemented as an add-on software to existing routing protocols and may be implemented in existing networks which use shortest path protocols, even where less than all of the routers use the data structure and multiple path scheme described herein.

Multiple path routing

Method for computing a shortest path tree structure for nodes in an interconnected network comprising the steps of maintaining a data structure T consisting of a set of edges e interconnecting the plurality of nodes in the network, each node having an associated parent node and distance value attributes; determining a weight change .DELTA. of an edge; obtaining a set of candidate nodes having associated parent and distance attributes that are affected by the weight change; selecting a node of the set of candidate nodes; identifying one or more descendents of the selected node and calculating a new distance attribute for each of the one or more descendents; searching for other nodes connected to the one or more identified descendent nodes and determining whether they should be included in the data structure T; and, repeating the selecting, identifying, calculating, searching and determining steps until all nodes of the set of candidate nodes are selected to update the data structure T.

Dynamic algorithms for shortest path tree computation

A router uses the destination address of its incoming packets to decide the proper outgoing interfaces by searching among all of the stored prefixes for the prefix which has the longest match when compared to the destination address in the packet. Prefix trees are employed to represent the set of prefixes to be searched and high-speed, longest prefix matches are performed. An efficient data structure compresses any prefix tree structure so that the number of memory accesses needed to find the longest prefix for any address depends only on the length of the prefix rather than on the number of stored prefixes. Illustratively, only four, 64-bit memory accesses are required to find the longest prefix match for each IPv4 address in the worst case, while only 3 Mbytes are required to store a 128K-entry routing table.

High speed routing using compressed tree process

A high speed router employs a hashed radix tree method for IP route look-up operations. The first k bits of an X bit IP address are hashed and used as an index to a RAM whose output is a pointer to the root node of one of a plurality of radix trees. Taking into account the subnet mask of the IP address, each of the radix trees examines the significant bits of the remaining X-k bits of the IP address for a match. Each match is stored in memory at least until a better match is found. If a best match is found a pointer to a second RAM is emitted, whose output is the best route. The tree can be constructed such that one or more bits can be examined simultaneously at each level. To gain the benefit of examining multiple bits at each level and minimize the required memory, a perfect hashing method is employed to eliminate unnecessary nodes in each tree.

Method for IP routing table look-up

A method for translating non internet unique addresses of a home network device to an internet unique address for internet communication through a router. Every device within a given home network is assigned three addresses:(i) a configured address identical to the network address of the router enabling access to an Internet; (ii) a logical address visible only to the other devices in the same home network; and (iii) a medium access control ('MAC') address. Every packet originating from a home network source device includes its MAC address, the router MAC address, its configured address and the network destination address, and is forwarded to its destination through the router. The router examines the network destination address to determine whether the communication is intranet or internet. For intranet communications the router replaces the configured address of the home network source device with the logical address of the home network source device, the logical address of the home network destination device with the configured address, its MAC address with the MAC address of the home network destination device, and forwards the packet to the home network destination device. For Internet communications the router forwards the packet along the Internet without replacing any of the source or destination information in the headers of the packet. Based on the source MAC address, however, the router records the logical address of the home network source device as well as the DA, SP, DP and PT in order to identify a response to the packet from the Internet destination device.

Growing community of inventors

Tinton Falls, NJ, United States of America

Hong-Yi Tzeng