Method and apparatus for generating routing information in a data communications network
First Claim
1. A method of generating routing information in a data communications network having, as elements, nodes and links, the method comprising the steps performed at a first network element of:
- receiving at the first network element information relating to a change in the network at a second network element,determining an affected set of network elements, wherein the affected set comprises network elements which are reachable from the second network element,determining a furthest network element in the affected set as located at a furthest distance from the first network element,identifying a sequence in which updating of routing information at each network element in the affected set should occur, andupdating the routing information at the first element in sequence.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus are disclosed for generating routing information in a data communications network. A first network element (such as a router) receives information relating to a second network element, such as another node or a network link. In response, the first network element determines whether the information relating to the second network element indicates a change in the network. When information relating to a second network element indicates a change in the network, the first network element determines a new shortest path through the network from the first network element for each network element in the network. After a delay, the first network element updates routing information for the first network element based on the new shortest path for the first network element. Preferably the delay is proportional to the distance of the first network element from the second network element.
-
Citations
46 Claims
-
1. A method of generating routing information in a data communications network having, as elements, nodes and links, the method comprising the steps performed at a first network element of:
-
receiving at the first network element information relating to a change in the network at a second network element, determining an affected set of network elements, wherein the affected set comprises network elements which are reachable from the second network element, determining a furthest network element in the affected set as located at a furthest distance from the first network element, identifying a sequence in which updating of routing information at each network element in the affected set should occur, and updating the routing information at the first element in sequence. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. An apparatus for generating routing information in a data communications network having, as elements, nodes and links, comprising:
-
means for receiving at a first network element information relating to a change in the network at a second network element, means for determining an affected set of network elements, wherein the affected set comprises network elements which are reachable from the second network element, means for determining a furthest network element in the affected set as located at a furthest distance from the first network element, means for identifying a sequence for updating of routing information at each network element in the affected set, and means for updating the routing information at the first element in sequence. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
-
-
33. An apparatus for generating routing information in a data communications network having as elements links and nodes, the apparatus comprising:
-
one or more processors; a network interface communicatively coupled to the processor and configured to communicate one or more packet flows among the processor and a network; and a computer readable medium comprising one or more sequences of instructions for generating routing information which instructions, when executed by one more processors, cause the one or more processors to generate routing information in a data communications network having, as elements, nodes and links, the method comprising the steps performed at a first network element of; receiving at the first network element information relating to a change in the network at a second network element, determining an affected set of network elements, wherein the affected set comprises network elements which are reachable from the second network element, determining a furthest network element in the affected set as located at a furthest distance from the first network element, identifying a sequence in which updating of routing information at each network element in the affected set should occur, and updating the routing information at the first element in sequence. - View Dependent Claims (34, 35, 36, 37, 38, 39)
-
-
40. A computer readable storage medium storing one or more sequences of instructions for a data communications network having, as elements, links and nodes, which instructions, when executed by one or more processors, cause the one or more processors to generate routing information in a data communications network having, as elements, nodes and links, the computer-readable storage medium comprising the steps performed at a first network element of:
-
receiving at the first network element information relating to a change in the network at a second network element, determining an affected set of network elements, wherein the affected set comprises network elements which are reachable from the second network element, determining a furthest network element in the affected set as located at a furthest distance from the first network element, identifying a sequence in which updating of routing information at each network element in the affected set should occur, and updating the routing information at the first element in sequence. - View Dependent Claims (41, 42, 43, 44, 45, 46)
-
Specification