Alcatel-lucent USA Inc.

Lucent Technologies Inc.

Alcatel Lucent

Sudipta Sengupta

Muralidharan Sampath Kodialam

Tirunell V Lakshman

Viswanath Poosala

Mansoor Ali Khan Alicherry

Peter Johannes Winzer

Iraj Saniee

Harsha S Nagesh

Peter Hessler

Walter Rothkegel

Tirnuell V Lakshman

In one embodiment, a method for supporting recovery from failure of a node in a network of nodes interconnected by links A set of two or more intermediate nodes (excluding the failed node) between an ingress point and an egress point is selected. Next, based on available bandwidth of the network, a non-zero fraction of the service level to route from the ingress point to each intermediate node is determined. Packets are then routed in two phases by: (1) determining one or more paths from the ingress point to each intermediate node for routing the corresponding fraction of the service level, and (2) determining one or more paths from each intermediate node to the egress point for routing the corresponding fraction of the service level.

Efficient and robust routing of potentially-variable traffic in IP-over-optical networks with resiliency against router failures

In one embodiment, a method for supporting recovery from failure of a path in a network of nodes interconnected by links. An intermediate node between an ingress point and an egress point of the network is selected to minimize the sum of (i) a capacity constraint between the ingress point and the intermediate node and (ii) a capacity constraint between the intermediate node and the egress point. The selection identifies two link-disjoint path sets, each comprising a backup path and at least one primary path, with a first path set between the ingress point and the intermediate node, and a second path set between the intermediate node and the egress point. To maximize network throughput, packets are routed in two phases, first to the intermediate node via the first path set in predetermined proportions, and then from the intermediate node to the final destination via the second path set.

Efficient and robust routing of potentially-variable traffic for path restoration following link failure

In one embodiment, a method for supporting recovery from failure of a link in a network of nodes interconnected by links. An intermediate node between an ingress point and an egress point of the network is selected to minimize the sum of (i) a capacity constraint between the ingress point and the intermediate node and (ii) a capacity constraint between the intermediate node and the egress point. The selection identifies two path structures, each comprising a primary path and one or more link backup detours protecting each link on the primary path, with a first path structure between the ingress point and the intermediate node, and a second path structure between the intermediate node and the egress point. To maximize network throughput, packets are routed in two phases, first to the intermediate node via the first path structure in predetermined proportions, and then from the intermediate node to the final destination via the second path structure.

Efficient and robust routing of potentially-variable traffic with local restoration against link failures

A scheme for routing packets of traffic to their destination after ensuring that they pass through one or more pre-determined intermediate nodes, thereby permitting all permissible traffic patterns to be handled without knowledge of the traffic matrix, subject to edge-link capacity constraints. In one embodiment, a request for a path with a service demand for routing data between the ingress point and the egress point is received. A set of two or more intermediate nodes between the ingress point and the egress point is selected. Based on a bandwidth of the network, respective fractions of the data to send from the ingress point to each node of the set of intermediate nodes are determined. The data is routed in the determined respective fractions from the ingress point to each node of the set of intermediate nodes, and routed from each node of the set of intermediate nodes to the egress point.

Efficient and robust routing independent of traffic pattern variability

Improved p-cycle restoration techniques using a signaling protocol are disclosed. For example, a technique for use in at least one node of a data communication network for recovering from a failure, wherein the data communication network includes multiple nodes and multiple links for connecting the multiple nodes, comprises the following steps/operations. Notification of the failure is obtained at the at least one node. A determination is made whether the failure is a single link failure or one of a node failure and a multiple link failure. A pre-configured protection cycle (p-cycle) plan is implemented when the failure is a single link failure but not when the failure is one of a node failure and a multiple link failure, such that two independent paths in the network are not connected when implementing the pre-configured protection cycle plan. Implementation of the pre-configured protection cycle plan may further comprise the node sending at least one message to another node in the data communication network and/or receiving at least one message from another node in the data communication network.

Signaling protocol for p-cycle restoration

The invention includes a method and apparatus for generating a link transmission schedule for handling traffic variation in wireless networks without dynamic scheduling or routing. The method includes determining fixed traffic capacities associated with respective wireless links of a wireless network according to a routing algorithm, and generating, using the routing algorithm and the fixed traffic capacities, a link transmission schedule including at least one condition by which traffic is transmitted using each of the network links. The link transmission schedule is adapted to remain substantially fixed during dynamic traffic changes. The routing algorithm may be a two-phase routing algorithm in which traffic is distributed by each node in the wireless network to every node in the wireless network using traffic split ratios. For two-phase routing, fixed traffic capacities may be determined using ingress and egress traffic capacities and traffic split ratios associated with respective nodes in the wireless network.

Method and apparatus for link transmission scheduling for handling traffic variation in wireless mesh networks

A given network of nodes that are interconnected by links having corresponding capacities has each link's capacity divided into working capacity and restoration capacity without a priori information about network traffic characteristics. Allocation of working capacity and restoration capacity for the network might be optimized by characterization of the network in accordance with a linear programming problem (LPP) subject to network constraints and then generating a solution to the LPP either exactly or with an approximation. Partitioning the capacity of each link in the network into working and restoration capacities minimizes the restoration capacity overhead in the network to allow for higher network utilization.

Traffic-independent allocation of working and restoration capacity in networks

A number of techniques are described for routing methods that improve resistance to faults affecting groups of links subject to common risks. One of these techniques accounts for failure potentials in physical networks by considering shared risk link groups separately from performance and costs metrics in determining a primary routing path and a backup path. A shared risk link group (SRLG) is an attribute attached to a link to identify edges that have physical links in common and can therefore be simultaneously disrupted due to a single fault. Another technique considers node disjointness and provides a solution of two paths that are as node disjoint as possible and minimizes administrative costs. The techniques may further be combined in a priority order thereby providing a solution of at least two paths that are strictly SRLG disjoint, as node-disjoint as possible, and have minimum administrative costs. Due to the priority order of evaluation and typical network physical configurations of links, with the links associated common fault SRLGs, the priority ordering technique is very efficient in determining at least two paths for routing between a source and destination node.

Methods of network routing having improved resistance to faults affecting groups of links subject to common risks

A computer-implemented method of computing throughput of a data-routing scheme for a network of nodes interconnected by links and having at least one ingress point and at least one egress point. The method includes: deriving a polynomial-size linear program from a combination of a first linear program and a second linear program and solving the polynomial-size linear program. The first linear program has infinite constraints and minimizes maximum-link utilization of a link in a path between the ingress point and the egress point. The second linear program determines whether any constraint of the first linear program is violated.

Maximum-throughput routing of traffic in the hose model

A load-balanced network architecture is disclosed in which a traffic flow deliverable from a source node to a destination node via intermediate nodes is split into parts, and the parts are distributed to respective ones of the intermediate nodes. Path delay differences for the parts are substantially equalized by delay adjustment at one or more of the intermediate nodes, and packets of one or more of the parts are scheduled for routing from respective ones of the intermediate nodes to the destination node based on arrival times of the packets at the source node.

Packet reorder resolution in a load-balanced network architecture

A network of nodes interconnected by links has content filtering specified at certain nodes, and routing of packet connections through the network is generated based on the specified content-filtering nodes. The network is specified via a content-filtering node placement method and a network-capacity maximization method so as to apply content filtering to packets for substantially all traffic (packet streams) carried by the network.

Routing for networks with content filtering

A packet network of interconnected nodes employs a method of routing with service-level guarantees to determine a path through the network for a requested multicast, label-switched path Each of the nodes includes one or more routers that forward packets based on a forwarding table constructed from a directed tree determined in accordance with the method of multicast routing with service-level guarantees. For a first implementation, a heuristic algorithm uses a scaling phase that iteratively adjusts a maximum arc capacity, determines the resulting tree for the iteration, and selects the tree as the routing tree that provides the &ldquo;maximum&rdquo; flow. For a second implementation, the heuristic algorithm computes maximum multicast flows and determines links in the network that are &ldquo;critical&rdquo; to satisfy future multicast routing requests. A multicast routing tree is selected such that provisioning the flows over its links &ldquo;minimally interferes&rdquo; with capacity of paths needed for future demands.

Growing community of inventors

Malden, MA, United States of America

Sudipta Sengupta