Mapping of routing traffic to switching networks

• US 6,055,561 A
• Filed: 09/30/1997
• Issued: 04/25/2000
• Est. Priority Date: 10/02/1996
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Viswanathan, Arun, Feldman, Nancy Karen, Woundy, Richard M., Boivie, Richard H.
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): YUAN, ALMARI ROMERO
• Application Number:
  US08/941,422
• Time in Patent Office: 938 Days
• Field of Search: 335/333, 370/17, 370/408, 370/409, 370/236, 370/221, 370/220, 370/402, 709/200, 709/238, 709/232, 709/227, 709/252, 379/370
• US Class Current: 709/200
• CPC Class Codes: H04L 12/4608 LAN interconnection over ATM networks
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/563 Signalling, e.g. protocols, reference model
• CPC Class Codes: H04L 2012/5665 Interaction of ATM with other protocols
• CPC Class Codes: H04L 2012/5667 IP over ATM
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/243 using M+N parallel active paths
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/602 Multilayer or multiprotocol switching, e.g. IP switching
• CPC Class Codes: H04L 49/606 Hybrid ATM switches, e.g. ATM&STM, ATM&Frame Relay or ATM&IP
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/168 : specially adapted for link layer protocols, e.g. asynchronous transfer mode [ATM], synchronous optical network [SONET] or point-to-point protocol [PPP]
• CPC Class Codes: H04Q 11/0478 : Provisions for broadband connections
• CPC Class Codes: Y02D 30/50 : in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

IP based networks use a number of different IP routing protocols to determine how packets ought to be routed. However, due to the rapid growth of the Internet, there is a great need for higher packet forwarding performance. This invention describes a way to map IP routing information onto a technology that uses label switching and swapping, such as ATM, without the need to change the network paradigm. This allows a network to continue to function and appear as a standard IP network, but with much higher performance. In this invention, an Integrated Switch Router (ISR), is a switch that has been augmented with standard IP routing support. The ISR at an entry point to the switching environment performs standard IP forwarding of datagrams, but the "next hop" of the IP forwarding table has been extended to include a reference to a switched path (for example, the VCC in ATM technology). Each switched path may have an endpoint at a neighboring router (comparable to existing IP next hops on conventional routers), or may traverse a series of ISRs along the best IP forwarding path, to an ISR endpoint. This allows datagrams to be switched at hardware speeds through an entire ISR network.

Claims

1. An apparatus for receiving and transmitting data units within a network of nodes, each data unit being associated with a destination address, said apparatus comprising:

a) at least one incoming port for receiving data units at said apparatus;

b) at least one outgoing port for transmitting data units from said apparatus;

c) a router device comprising a router database for mapping said destination address to an outgoing port, said router database being stored in a storage device; and

d) a linking database for mapping said destination address to a label associated with an outgoing port, said linking database being stored in a storage device, wherein one or a plurality of destination addresses are mapped to one or a plurality of labels, to build one or a plurality of switched connections in said network.

2. An apparatus as set forth in claim 1, further comprising:

e) a switching device comprising a switching database for mapping a label within a received data unit to an outgoing port, said switching database being stored in a storage device.

3. An apparatus as set forth in claim 1 or 2 wherein the router database is comprised of a forwarding database.

4. An apparatus as set forth in claim 1 or 2 wherein the router database is comprised of an IP forwarding information database.

5. An apparatus as set forth in claim 1 or 2, wherein a plurality of said destination addresses are mapped to a single label and an outgoing port.

6. An apparatus as set forth in claim 1 or 2 wherein each entry in the linking database corresponds to an entry in the router database.

7. An apparatus as set forth in claim 1 or 2, wherein a plurality of said destination addresses are mapped to a single label and an outgoing port and wherein each entry in the linking database corresponds to an entry in the router database.

8. An apparatus as set forth in claim 1 or 2 wherein said data unit is a member of the group consisting of an ATM cell, an AAL5 frame, a data-link layer frame, a frame-relay frame, a network layer packet, an IP version 4 datagram, and an IP version 6 datagram.

9. A method of receiving and transmitting data units by building one or more switched connections by distributing and using labels within a network of nodes, said labels being assigned to network addresses by nodes within a network, wherein an initial node initiates a set-up message to every node adjacent to said initial node, the set-up message identifying a network address and an assigned label, and wherein each node in the network comprises at least one incoming and at least one outgoing port, a router device with a routing database, a switching device with a switching database, said method comprising:

a) each node that receives said set-up message then testing from its routing database, for the network address in the set-up message, whether said set-up message arrived from an adjacent node in the direction of the network address,

b) each receiving node on which the test set forth in step(a) succeeds, and which has adjacent nodes other than the one from which the set-up message was received, then assigns a second label for each said adjacent node,

c) each receiving node then transmits thereto a set-up message comprising the received network address and the newly assigned second label,

d) each receiving node which transmits a set-up message as set forth in step (c), creates entries in the switching database to switch data units between the second labels assigned in step (b) and the label received in the set-up message, and

e) each node of the network repeating steps (a) through (d) upon receiving any set-up message from any node other than the initiating node,

wherein one or a plurality of destination addresses are mapped to one or a plurality of labels, to build said one or more switched connections in said network.

10. A method as set forth in claim 9, and wherein each node in the network further comprises a linking database, said method further comprising:

f) each receiving node on which the test set forth in step (a) succeeds, and which is to initiate transmission of data units using the label in the set-up message, then associates in the linking database each routing database entry associated with said network address, with the label in said message.

11. A method as set forth in claim 9 or 10, further comprising said receiving node that fails the test set forth in step (a) sending a rejection message to the neighboring node from which it received said message.

12. A method as set forth in claim 9 wherein the set-up message comprises an explicit list of said network addresses, said method further comprising:

g) the testing as set forth in step (a) is performed for each explicitly listed network address,

h) each node carries out step (b) only when at least one explicitly listed network address succeeds the test as set forth in step (a), and

i) each node carries out step (c), wherein the set-up message sent to the neighboring node(s) lists only those network addresses that succeed the test as set forth in step (a).

13. A method as set forth in claim 10 wherein the set-up message comprises an explicit list of said network addresses, said method further comprising:

g) the testing as set forth in step (a) is performed for each explicitly listed network address,

h) each node carries out step (b) only when at least one explicitly listed network address succeeds the test as set forth in step (a),

i) each node carries out step (c), wherein the set-up message sent to the neighboring node(s) lists only those network addresses that succeed the test as set forth in step (a), and

j) each node carries out step (f) only for each explicitly listed network address that succeeds the test as set forth in step (a).

14. A method as set forth in claim 9, 10 or 12, wherein the set-up message comprises a representative identifier which represents at least one network address.

15. A method as set forth in claim 9, 10, 12 or 13 wherein a plurality of set-up messages are carried within a single set-up message.

26. A method as set forth in claim 9, 10, 12, 13, 16, 17, 20, 21, 22 or 23 wherein said initiating node comprises one of a network egress node, a network ingress node, and a network routing boundary node.

27. A method as set forth in claim 9, 10, 12, 13, 16, 17, 20, 21, 22 or 23 wherein said network address is a member selected from the group consisting of a destination address, a network prefix, a Network Layer Routing Information (NLRI) address, a Classless Inter-Domain Routing (CIDR) address, a multicast group address, a multicast (source, group) address, a link-state routing protocol node identifier, an Open Shortest Path First protocol'"'"'s router identifier, and an IP network address.

28. A method as set forth in claim 9, 10, 12, 13, 16, 17, 20, 21, 22, or 23 wherein said routing database comprises a forwarding database or an IP forwarding information database.

16. A method of receiving and transmitting data units using labels within a network of nodes by building one or more switched connections by requesting said labels, said labels being assigned to network addresses by nodes within a network, wherein each node in the network comprises at least one incoming and at least one outgoing port, a router device with a routing database, a switching device with a switching database, a linking database mapping a network address to a label, said method comprising:

a) a node sends a request message to a neighboring node for a label for a network address in the routing database,

b) each node receiving a request message that does not have a label in its linking database for the network address in said request message discards said request message, and

c) each node receiving a request message that has a label in its linking database for the network address in the said request message responds with a message containing said label,

wherein one or a plurality of destination addresses are mapped to one or a plurality of labels, to build said one or more switched connections in said network.

17. A method as set forth in claim 16, further comprising said receiving node sending a reject message to the requesting node when step (b) is executed.

18. A method as set forth in claim 16 or 17, wherein the request message comprises a representative identifier which represents at least one network address.

19. A method as set forth in claim 16 or 17, wherein a plurality of request messages are carried within a single request message.

20. A method of removing one or more switched connections by withdrawing labels assigned to one or more network addresses by nodes within a network, wherein each node in the network comprises at least one of incoming and at least one outgoing port, a router device with a routing database, a switching device with a switching database, and wherein each node which is to withdraw an assigned label for a network address removes the existing corresponding entry from the switching database and sends as sending node a withdraw message to a neighboring node, said message containing said network address and said label, said method comprising:

a) each said node receiving the said withdraw message thereupon testing via the routing database that said message arrived from a neighboring node in the direction of the network address in said message,

b) said receiving node testing that said label exists in the switching database,

c) each said receiving node on which the tests as set forth in step (a) and step (b) succeeds, then sends a withdraw message to its neighboring nodes for which a switching database entry exists that corresponds to said label, and

d) each said node on which the test set forth in step (a) and step (b) succeeds then removes the switching database entry between the sending node'"'"'s label and the label assigned to each said neighboring node,

wherein one or a plurality of destination addresses are mapped to one or a plurality of labels, to remove said one or more switched connections in said network.

21. A method as set forth in claim 20, further comprising said receiving node sending a reject message to said sending node in the event that said receiving node fails the test as set forth in step (a) or step (b).

24. A method as set forth in claim 20, 21, 22, or 23 wherein the withdraw message comprises a representative identifier which represents at least one network.

25. A method as set forth in claim 20, 21, 22, or 23 wherein a plurality of withdraw messages are carried within a single withdraw message.

22. A method of removing one or more switched connections by withdrawing labels assigned to one or more network addresses by nodes within a network, wherein each node in the network comprises at least one incoming port and at least one outgoing port, a router device with a routing database, a switching device with a switching database, a linking database which maps a routing database entry to a label, and wherein each node which is to withdraw an assigned label for a network address removes the existing corresponding entry from the switching database and sends as sending node a withdraw message to a neighboring node, said message containing said network address, said method comprising:

a) each said node receiving said withdraw message thereupon testing via the routing database that said message arrived from a neighboring node in the direction of the network address in said message,

b) each said receiving node on which the tests as set forth in step (a) succeeds, then sends a withdraw message to its neighboring nodes for which a switching database entry exists that corresponds to said label,

c) each said node on which the test set forth in step (a) succeeds then removes each existing switching database entry between the sending node'"'"'s label and the label assigned to each said neighboring node, and

d) each said node receiving said withdraw message on which the test as set forth in (a) succeeds then removes each existing corresponding label from the linking database for the network address,

wherein one or a plurality of destination addresses are mapped to one or a plurality of labels, to remove said one or more switched connections in said network.

23. A method as set forth in claim 22, further comprising said receiving node sending a reject message to said sending node in the event that said receiving node fails the test as set forth in step (a).

29. A program storage device readable by a computing machine, tangibly embodying a program of instructions executable by the machine to perform method steps of a method of receiving and transmitting data units by building one or more switched connections by distributing and using labels within a network of nodes, said labels being assigned to network addresses by nodes within a network, wherein an initial node initiates a set-up message to every node adjacent to said initial node, the set-up message identifying a network address by and an assigned label, and wherein each node in the network comprises at least one incoming and at least one outgoing port, a router device with a routing database, a switching device with a switching database, said method comprising:

a) each node that receives said set-up message then testing from its routing database, for the network address in the set-up message, whether said set-up message arrived from an adjacent node in the direction of the network address,

b) each receiving node on which the test set forth in step (a) succeeds, and which has adjacent nodes other than the one from which the set-up message was received, then assigns a second label for each said adjacent node,

c) each receiving node then transmits thereto a set-up message comprising the received network address and the newly assigned second label,

d) each receiving node which transmits a set-up message as set forth in step (c), creates entries in the switching database to switch data units between the second labels assigned in step (b) and the label received in the set-up message, and

e) each node of the network repeating steps (a) through (d) upon receiving any set-up message from any node other than the initiating node,

wherein one or a plurality of destination addresses are mapped to one or a plurality of labels, to build said one or more switched connections in said network.

30. A program storage device as set forth in claim 29, and wherein each node in the network further comprises a linking database, further comprising:

f) each receiving node on which the test set forth in step (a) succeeds, and which is to initiate transmission of data units using the label in the set-up message, then associates in the linking database each routing database entry associated with said network address, with the label in said message.

31. A program storage device as set forth in claim 29 or 30, further comprising said receiving node that fails the test set forth in step (a) sending a rejection message to the neighboring node from which it received said message.

32. A program storage device as set forth in claim 29 wherein the set-up message comprises an explicit list of said network addresses, further comprising:

g) the testing as set forth in step (a) is performed for each explicitly listed network address,

h) each node carries out step (b) only when at least one explicitly listed network address succeeds the test as set forth in step (a), and

i) each node carries out step (c), wherein the set-up message sent to the neighboring node(s) lists only those network addresses that succeed the test as set forth in step (a).

33. A program storage device as set forth in claim 30 wherein the set-up message comprises an explicit list of said network addresses, further comprising:

g) the testing as set forth in step (a) is performed for each explicitly listed network address,

h) each node carries out step (b) only when at least one explicitly listed network address succeeds the test as set forth in step (a),

i) each node carries out step (c), wherein the set-up message sent to the neighboring node(s) lists only those network addresses that succeed the test as set forth in step (a), and

j) each node carries out step (f) only for each explicitly listed network address that succeeds the test as set forth in step (a).

34. A program storage device as set forth in claim 29, 30 or 32, wherein the set-up message comprises a representative identifier which represents at least one network address.

35. A program storage device as set forth in claim 29, 30, 32 or 33 wherein a plurality of set-up messages are carried within a single set-up message.

46. A program storage device as set forth in claim 29, 30, 32, 33, 36, 37, 40, 41, 42 or 43 wherein said initiating node comprises one of a network egress node, a network ingress node, and a network routing boundary node.

47. A program storage device as set forth in claim 29, 30, 32, 33, 36, 37, 40, 41, 42 or 43 wherein said network address is a member selected from the group consisting of a destination address, a network prefix, a Network Layer Routing Information (NLRI) address, a Classless Inter-Domain Routing (CIDR) address, a multicast group address, a multicast (source, group) address, a link-state routing protocol node identifier, an Open Shortest Path First protocol'"'"'s router identifier, and an IP network address.

48. A program storage device as set forth in claim 29, 30, 32, 33, 36, 37, 40, 41, 42 or 43 wherein said routing database comprises a forwarding database and an IP forwarding information database.

36. A program storage device readable by a computing machine, tangibly embodying a program of instructions executable by the machine to perform method steps of a method of receiving and transmitting data units using labels within a network of nodes by building one or more switched connections by requesting said labels, said labels being assigned to network addresses by nodes within a network, wherein each node in the network comprises at least one incoming and at least one outgoing port, a router device with a routing database, a switching device with a switching database, a linking database mapping a network address to a label, said method comprising:

a) a node sends a request message to a neighboring node for a network address in the routing database,

b) each node receiving a request message that does not have a label in its linking database for the network address in said request message discards said request message, and

c) each node receiving a request message that has a label in its linking database for the network address in said request message responds with a message containing said label,

wherein one or a plurality of destination addresses are mapped to one or a plurality of labels, to build said one or more switched connections in said network.

37. A program storage device as set forth in claim 36, further comprising said receiving node sending a reject message to the requesting node when step (b) is executed.

38. A program storage device as set forth in claim 36 or 37, wherein the request message comprises a representative identifier which represents at least one network address.

39. A program storage device as set forth in claim 36 or 37, wherein a plurality of request messages are carried within a single request message.

40. A program storage device readable by a computing machine, tangibly embodying a program of instructions executable by the machine to perform method steps of a method of removing one or more switched connections by withdrawing labels assigned to one or more network addresses by nodes within a network, wherein each node in the network comprises at least one incoming port and at least one outgoing port, a router device with a routing database, a switching device with a switching database, and wherein each node which is to withdraw an assigned label for a network address removes the existing corresponding entry from the switching database and sends as sending node a withdraw message to a neighboring node, said message containing said network address and said label, said method comprising:

a) each said node receiving said withdraw message thereupon testing via the routing database that said message arrived from a neighboring node in the direction of the network address in said message,

b) said receiving node testing that said label exists in the switching database,

c) each said receiving node on which the tests as set forth in step (a) and step (b) succeeds, then sends a withdraw message to its neighboring nodes for which a switching database entry exists that corresponds to said label, and

d) each said node on which the test set forth in step (a) and step (b) succeeds then removes the switching database entry between the sending node'"'"'s label and the label assigned to each said neighboring node,

wherein one or a plurality of destination addresses are mapped to one or a plurality of labels, to remove said one or more switched connections in said network.

41. A program storage device as set forth in claim 40, further comprising said receiving node sending a reject message to said sending node in the event that said receiving node fails the test as set forth in step (a) or step (b).

44. A program storage device as set forth in claim 40, 41, 42, or 43 wherein the withdraw message comprises a representative identifier which represents at least one network.

45. A program storage device as set forth in claim 40, 41, 42, or 43 wherein a plurality of withdraw messages are carried within a single withdraw message.

42. A program storage device readable by a computing machine, tangibly embodying a program of instructions executable by the machine to perform method steps of a method of removing one or more switched connections by withdrawing labels assigned to one or more network addresses by nodes within a network, wherein each node in the network comprises at least one incoming port and at least one outgoing port, a router device with a routing database, a switching device with a switching database, a linking database which maps a routing database entry to a label, and wherein each node which is to withdraw an assigned label for a network address removes the existing corresponding entry from the switching database and sends as sending node a withdraw message to a neighboring node, said message containing said network address, said method comprising:

a) each said node receiving the said withdraw message thereupon testing via the routing database that said message arrived from a neighboring node in the direction of the network address in said message,

b) each said receiving node on which the tests as set forth in step (a) succeeds, then sends a withdraw message to its neighboring nodes for which a switching database entry exists that corresponds to said label,

c) each said node on which the test set forth in step (a) succeeds then removes each existing switching database entry between the sending nodes label and the label assigned to each said neighboring node, and

d) each said node receiving said withdraw message on which the test as set forth in (a) succeeds then removes each existing corresponding label from the linking database for the network address,

wherein one or a plurality of destination addresses are mapped to one or a plurality of labels, to remove said one or more switched connections in said network.

43. A program storage device as set forth in claim 42, further comprising said receiving node sending a reject message to said sending node in the event that said receiving node fails the test as set forth in step (a).