Splitting and sharing routing information among several routers acting as a single border router

• US 9,497,113 B2
• Filed: 09/08/2015
• Issued: 11/15/2016
• Est. Priority Date: 08/22/2002
• Status: Expired due to Term

• Current Assignee: Kyndryl Incorporated (Kyndryl Holdings, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Dispensa, Jean-Claude, Lund, Arnaud
• Primary Examiner(s): Lee, Andrew
• Application Number:
  US14/847,105
• Publication Number:
  US 20150381482A1
• Time in Patent Office: 434 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/44 Distributed routing

Abstract

Routers split and share routing information among several routers within a group of routers acting as a single border router in an Internet protocol (IP) network, each router comprising a routing table. A router of the group selects routes in the routing table of the router; requests other routers of the group to replace, in their routing tables, each selected route with the router as next hop; associates parts of-non selected routes, each one with another router of the group; and removes and replaces, in the routing table, each-non selected route associated with a router of the group by the associated router as next hop.

Claims

1. A computer-implemented method for splitting and sharing routing information among routers, the method comprising executing on a router the steps of:

in response to a size of a routing table of a first border router exceeding a predefined threshold, splitting the routing table into a plurality of subnetworks, wherein the first border router acts as a single border router in internet protocol network communication with a group of other border routers;

assigning responsibility for routing internet protocol network communication traffic intended for a first subnetwork of the plurality of subnetworks to the first border router;

informing each of the group of border routers that the first border router is ready to receive internet protocol network communication traffic from the each of the other border routers that is directed to the first subnetwork; and

instructing each of the other border routers of the group of border routers to select and remove from their own routing tables at least one route related to the first subnetwork and replace the removed at least one route by a single route pointing to the first border router as next hop.

2. The method of claim 1, further comprising:

a service provider configuring the first border router to perform the steps of splitting the routing table into the plurality of subnetworks in response to the size of the routing table of the first border router exceeding the predefined threshold, assigning responsibility for routing internet protocol network communication traffic intended for the first subnetwork of the plurality of subnetworks to the first border router, informing each of the group of border routers that the first border router is ready to receive internet protocol network communication traffic from the each of the other border routers that is directed to the first subnetwork, and instructing each of the other border routers of the group of border routers to select and remove from their own routing tables the at least one route related to the first subnetwork and replace the removed at least one route by the single route pointing to the first border router as next hop.

3. The method according to the claim 1, wherein the selected and removed at least one route is a plurality of routes that are each under the responsibility of the first border router.

4. The method according to claim 3, wherein the step of selecting the plurality of routes comprises selecting a plurality of contiguous internet protocol network addresses within a given address range.

5. The method of claim 1, further comprising:

assigning responsibility for routing internet protocol network communication traffic intended for another subnetwork of the plurality of subnetworks to a second router of the group of border routers;

informing each of other routers of the group of border routers that the second router is ready to receive internet protocol network communication traffic from the each of the other border routers that is directed to the another subnetwork; and

instructing each of the other routers of the group of border routers to select and remove from their own routing tables at least one route related to the another subnetwork and replace the removed at least one route by a single route pointing to the second router of the group of routers.

6. The method of claim 1, further comprising:

establishing exterior border gateway protocol sessions between each of the group of border routers and each of a group of neighbor routers; and

establishing internal border gateway protocol sessions between each of the group of border routers with each of other ones of the group of border routers.

7. The method of claim 6, wherein the step of establishing the internal border gateway protocol sessions causes each router of the group of border routers to build ordered lists of active routers of the group of border routers.

8. The method of claim 6, further comprising:

assigning responsibility for routing internet protocol network communication traffic intended for each of the plurality of subnetworks to one each of the group of border routers.

9. A computer system router, comprising:

a hardware memory device comprising a first routing table stored thereon;

wherein the router is in internet protocol network communication with a group of other border routers and acts as a single border router, and in response to a size of the first routing table exceeding a predefined threshold;

splits the routing table into a plurality of subnetworks;

assigns responsibility for routing internet protocol network communication traffic intended for a first subnetwork of the plurality of subnetworks to itself as a first border router;

informs each of the group of border routers that it is ready to receive internet protocol network communication traffic from the each of the other border routers that is directed to the first subnetwork as the first border router; and

instructs each of the other border routers of the group of border routers to select and remove from their own routing tables at least one route related to the first subnetwork and replace the removed at least one route by a single route pointing to the router as the first border router as next hop.

10. The computer system router according to claim 9, wherein the selected and removed at least one route is a plurality of routes that are each under the responsibility of the first border router.

11. The computer system router according to claim 10, wherein the router selects a plurality of contiguous internet protocol network addresses within a given address range as the plurality of selected and removed routes.

12. The computer system router according to claim 10, wherein the router further:

assigns responsibility for routing internet protocol network communication traffic intended for another subnetwork of the plurality of subnetworks to a second router of the group of border routers;

informs each of other routers of the group of border routers that the second router is ready to receive internet protocol network communication traffic from the each of the other border routers that is directed to the another subnetwork; and

instructs each of the other routers of the group of border routers to select and remove from their own routing tables at least one route related to the another subnetwork and replace the removed at least one route by a single route pointing to the second router of the group of routers.

13. The computer system router according to claim 12, wherein the router further:

establishes exterior border gateway protocol sessions with each of a group of neighbor routers; and

establishes internal border gateway protocol sessions with each of other ones of the group of border routers.

14. The computer system router according to claim 13, wherein establishment of the internal border gateway protocol sessions causes each router of the group of border routers to build ordered lists of active routers of the group of border routers.

15. A computer program product, comprising:

a hardware memory device comprising a first routing table and instructions stored thereon for execution on a first router;

wherein the instructions cause the first router to act as a single border router in communication with a group of other routers in an internet protocol network, and to;

in response to a size of the first routing table exceeding a predefined threshold, split the routing table into a plurality of subnetworks;

assign responsibility for routing internet protocol network communication traffic intended for a first subnetwork of the plurality of subnetworks to itself as a first border router;

inform each of the group of border routers that it is ready to receive internet protocol network communication traffic from the each of the other border routers that is directed to the first subnetwork as the first border router; and

instruct each of the other border routers of the group of border routers to select and remove from their own routing tables at least one route related to the first subnetwork and replace the removed at least one route by a single route pointing to the router as the first border router as next hop.

16. The computer program product according to claim 15, wherein the selected and removed at least one route is a plurality of routes that are each under the responsibility of the first border router.

17. The computer program product according to claim 15, wherein the instructions for execution on the first router, further cause the first router to select a plurality of contiguous internet protocol network addresses within a given address range as the plurality of selected and removed routes.

18. The computer program product according to claim 15, wherein the instructions for execution on the first router, further cause the first router to:

assign responsibility for routing internet protocol network communication traffic intended for another subnetwork of the plurality of subnetworks to a second router of the group of border routers;

inform each of other routers of the group of border routers that the second router is ready to receive internet protocol network communication traffic from the each of the other border routers that is directed to the another subnetwork; and

instruct each of the other routers of the group of border routers to select and remove from their own routing tables at least one route related to the another subnetwork and replace the removed at least one route by a single route pointing to the second router of the group of routers.

19. The computer program product according to claim 18, wherein the instructions for execution on the first router, further cause the first router to:

establish exterior border gateway protocol sessions with each of a group of neighbor routers; and

establish internal border gateway protocol sessions with each of other ones of the group of border routers.

20. The computer program product according to claim 19, wherein establishment of the internal border gateway protocol sessions causes each router of the group of border routers to build ordered lists of active routers of the group of border routers.