Cisco Technology, Inc.

Steven Vincent Luong

Heidi H Ou

Stefano Benedetto Previdi

Manish Bhardwaj

Jan Medved

James L Ng

Steven Edward Moore

Jining Tian

Rena Whei-Ming Yang

Gerald Redwine

Kevin M Eckhardt

Scott R Sturgess

Jiang Zhu

Bruce Stuart Davie

Gargi Nalawade

Huida Dai

Zhunian Zhang

Christopher Losack

Sandy Ng

Rena W Yang

Xiang Zheng

In one embodiment, a first network device may receive a request for an identifier of at least one target to service a client. The first network device may obtain an identifier of each of two or more targets. The first network device may then determine whether to redirect the request. The first network device may redirect the request to a second network device according to a result of the determining step, where the first network device is in a first autonomous system and the second network device is in a second autonomous system.

Redirection of requests for target addresses

In one embodiment, a node in a computer network joins a global ring associated with a distributed hash table (DHT), and maintains a DHT routing table and DHT database for the global ring. In addition, the node may determine a particular service class for which the node is configured, and may join a particular service-based sub-ring according to the particular service class, where all nodes of the particular service-based sub-ring are within the global ring. As such, a service-based DHT routing table and service-based DHT database may be maintained for the particular service-based sub-ring, such that DHT operations identified by the particular service class are routed to the particular service-based sub-ring (e.g., by a portal node).

Service-aware distributed hash table routing

In one embodiment, a method comprises identifying prefix groups for searchable character symbols, each prefix group having a corresponding searchable character symbol comprising at least one searchable character; assigning at least one prefix group to each of a plurality of distributed hash table nodes in a network, each distributed hash table node containing at least one of the prefix groups, each distributed hash table node assigned a corresponding prescribed keyspace range of a prescribed keyspace, each distributed hash table node configured for storing data records having respective primary data record keys within the corresponding prescribed keyspace range; and assigning secondary indexes that start with one of the searchable character symbols to the corresponding prefix group in the associated distributed hash table node, enabling any prefix search starting with the one searchable character symbol to be directed to the corresponding prefix group in the associated distributed hash table node.

Prefix and predictive search in a distributed hash table

According to one embodiment, an apparatus that makes improved routing decisions is provided that includes a receiver, a retriever, a proximity engine, and a transmitter. The receiver may be configured to receive a request from a source. The retriever may be configured to retrieve a plurality of providers capable of servicing the request. The proximity engine may be configured to rank the plurality of providers based on weights indicative of a network distance. The weights may correspond to a first Border Gateway Protocol (BGP) community attribute associated with the source and at least a second BGP community attribute associated with at least one of the providers in the plurality of providers. The transmitter may be configured to transmit the request to the provider in the plurality of providers with the highest ranking.

Method and apparatus for routing requests for service using BGP community attributes

A node in an overlay network requests a ranked list of other nodes in multiple areas of the overlay network that can provide a desired piece of content or service to the requesting node. A separate node such as a router generates the ranked list using a routing algorithm, returning the list to the requesting node so that the requesting node may acquire the desired content or service from the nearest node in the overlay network.

Routing-based proximity for communication networks

A method, system, apparatus and machine-readable medium for transmitting a packet through a network to convey network topology is provided. The method includes the step of generating at least one link state protocol data unit (LSP) with a first identifier until reaching a maximum sequence number in a sequence assigned to a network device, represented by the first identifier. The method further includes the step of modifying the first identifier to produce a second identifier. The method also includes the step of generating at least one LSP with the second identifier, and with a sequence number that is less than or equal to the maximum sequence number in the sequence. The system for transmitting a packet through a network, to convey network topology, comprises the means for performing the above-mentioned method steps.

Method and system to restart IS-IS when LSP wraps

A node in an overlay network requests a ranked list of other nodes in the overlay network that can provide a desired piece of content or service to the requesting node. A separate node such as a router generates the ranked list using a routing algorithm, returning the list to the requesting node so that the requesting node may acquire the desired content or service from the nearest node in the overlay network.

Routing-based proximity for communication networks to routing-based proximity for overlay networks

Disclosed are methods and apparatus for flooding link state packets or packet data units (LSP's) from a first node to one other LSP receiving node, where the LSP's are flooded in an order that is related to relative costs of various paths emanating from the first node. That is, the first node sends its own LSP first since the first node has no cost relative to itself. The first node then sends other LSP's that are associated with a plurality of other LSP sending nodes that have previously flooded their LSP's to the first node. These other LSP's are sent by the first node to the other LSP receiving node in an order related to the relative costs associated with the paths from the first node to each of the other LSP sending nodes which had previously sent the other LSP's to the first node.

Method and apparatus for flooding link state packets to achieve faster convergence

In a link state protocol such as an interior gateway protocol (IGP), link state advertisements or link state packets (LSA/LSPs) are sent only to network nodes that have expressed interest in them, rather than always flooding them.

Selectively sending link state messages in a network link state protocol based on interest of network nodes

Methods, systems, and apparatuses for transmitting link state packet (LSP) through a network are provided. The method includes dividing the LSP into LSP fragments having respective fragment numbers, transmitting the LSP fragments repetitively through the network, identifying at least one LSP fragment that is updated while the LSP fragments are being transmitted, and retransmitting the identified LSP fragments. The transmitted updated LSP is used for processing the Shortest Path First algorithm to identify accurately the shortest path that can be used to establish communication in the network.

Method and system for transmitting LSP fragments

Disclosed are methods and apparatus for flooding link state packets or packet data units (LSP's) from a first node to one other LSP receiving node, where the LSP's are flooded in an order that is related to relative costs of various paths emanating from the first node. That is, the first node sends its own LSP first since the first node has no cost relative to itself. The first node then sends other LSP's that are associated with a plurality of other LSP sending nodes that have previously flooded their LSP's to the first node, and these other LSP's are sent by the first node to the other LSP receiving node in an order related to the relative costs associated with the paths from the first node to each of the other LSP sending nodes which had previously sent the other LSP's to the first node.

Disclosed are methods and apparatus for handling Link State Packets (LSPs) sent between processing nodes within a computer network. At a first node, an LSP sent by a second node is received. The received LSP specifies connectivity information regarding the second node. It is then determined whether one of two conditions is met: either the received LSP is an updated LSP even though it appears older and a corresponding stored LSP fails authentication, or the received LSP fails authentication and it appears newer. If it is determined that one of these conditions is met, as well as purging criteria, then updating procedures are then performed on the LSP information that is maintained by the first node, where the LSP information was originally obtained from a corresponding LSP sent by the second node.

Apparatus and methods for updating stale link state packets and routing table entries

A system and method are disclosed for determining when to set up or tear down such a temporary transit path so that temporary transit paths are set up when they are needed and torn down when they are no longer needed. A temporary transit path is set up when the bit rate exceeds a first threshold. The temporary transit path is torn down when the bit rate is less than a second threshold. The temporary transit path is set up or torn down between a source station's router and a next hop router. The temporary transit path is set up within a subnetwork that includes the source station, the next hop router, and an intermediate router that is interconnected by a plurality of permanent transit paths to the source station and the next hop router. In one embodiment, a method for creating a temporary path for data packet transmission in the subnetwork is disclosed. Transmission of the data packets is initiated over the permanent transit paths that are coupled between the source station and the next hop router. A bit rate of the data packets from the source station to the next hop router is measured after initiating the transmission. Data packets transmission over the permanent transit paths is continued when the measured bit rate is below a first predetermined value. A temporary transit path between the source station and the next hop router is created when the measured bit rate is above the first predetermined value. The data packets are transmitted over the created temporary transit path when the measured bit rate is above the first predetermined value. In a preferred embodiment, the bit rate is measured again after creating the temporary transit path and transmitting the data packets over the created temporary transit path. The created temporary transit path is torn down when the bit rate is below the second predetermined value. Transmission of the data packets is sent over the permanent transit paths from the source station to the next hop routers once the temporary transit path is torn down.

Growing community of inventors

San Jose, CA, United States of America

Steven Vincent Luong