General internet method for routing packets in a communications network

• US 5,353,283 A
• Filed: 05/28/1993
• Issued: 10/04/1994
• Est. Priority Date: 05/28/1993
• Status: Expired due to Term

• Current Assignee: TTI Inventions A LLC (Intellectual Ventures LLC)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Tsuchiya, Paul F.
• Primary Examiner(s): Safourek, Benedict V.
• Application Number:
  US08/069,275
• Time in Patent Office: 494 Days
• Field of Search: 340/827, 370/16, 370/54, 370/60, 370/94.1, 370/94.3, 370/60.1, 370/85.13, 370/85.14
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/34 Source routing

Abstract

A method for transmitting a packet via a sequence of nodes in a network is disclosed. The transmitted-packet contains a sequence of one or more identifiers in a sequence of fields 410, 420, 430, 440, 450, 460, 470, 480 and a pointer pointing to a particular identifier in the sequence of identifiers in a field 485 of a routing section of a header in the packet. A node of the sequence of nodes at which the packet is located selects a forwarding table from a set of forwarding tables maintained in a memory at that node. The node then retrieves an entry from the selected forwarding table indexed by the identifier in the sequence of identifiers pointed to by the pointer. The node then transmits the packet to the next node of the sequence of nodes indicated by the retrieved forwarding table entry.

Claims

1. A method for transmitting via a sequence of nodes in a network a packet containing a sequence of identifiers and a pointer pointing to a particular identifier in said sequence of identifiers comprising the steps of:

at one of said nodes in which said packet is located, selecting a particular forwarding table from a set of forwarding tables maintained in a memory at said one node,

retrieving an entry from said selected forwarding table in response to said particular identifier pointed to by said pointer, and

transmitting said packet to a second node of said sequence of nodes indicated by said retrieved entry.

2. The method of claim 1 wherein said packet further comprises a routing context parameter and wherein said forwarding table is selected in response to said routing context parameter.

3. The method of claim 1 further comprising the step of, in response to said retrieved entry, changing said pointer to a different pointer which points to a different identifier in said sequence of identifiers.

4. The method of claim 3 further comprising the steps of:

receiving said packet at said second node of said sequence of nodes,

at said second node, selecting a second forwarding table from a second set of forwarding tables maintained in a memory at said second node,

retrieving an entry from said second selected forwarding table in response to said different identifier pointed to by said different pointer, and

transmitting said packet to a third node of said sequence of nodes indicated by said entry retrieved from said second selected forwarding table.

5. The method of claim 1 wherein said packet is a multicast packet and wherein said node transmits each of a plurality of copies of said packet to a different node.

6. The method of claim 2 further comprising the step of modifying said routing context parameter in said packet to select a particular forwarding table at each successive node of said sequence of nodes via which said packet is transmitted.

7. The method of claim 2 further comprising the step of modifying said routing context parameter to reroute said packet around congestion in said sequence of nodes via which said packet is transmitted.

8. The method of claim 2 further comprising the step of modifying said routing context parameter in response to said retrieved entry.

9. The method of claim 2 wherein said routing context parameter identifies a desired transmission delay of said packet in said network.

10. The method of claim 1 wherein said network is an internet.

11. The method of claim 10 wherein said internet comprises a plurality of backbone networks which backbone networks contain at least one interconnected node, wherein said sequence of nodes via which said packet is transmitted includes at least one node contained in at least one of said backbone networks, and wherein said sequence of identifiers comprises one identifier associated with each of said backbone networks containing at least one of said nodes via which said packet is transmitted.

12. The method of claim 1 wherein at least one of said identifiers in said sequence of identifiers is a virtual path identifier.

13. The method of claim 2 wherein said routing context parameter identifies a quality of service for transmitting said packet in said network.

14. A method for transmitting via a sequence of nodes a packet containing a routing context parameter comprising the steps of:

at one of said nodes in which said packet is located, selecting a forwarding table from a set of forwarding tables maintained in a memory at said one node, which forwarding table is selected in response to said routing context parameter,

retrieving an entry from said selected forwarding table in response to routing information contained in the packet, and

transmitting said packet to a second node of said sequence of nodes indicated by said retrieved entry.

15. The method of claim 14 wherein said routing information comprises a sequence of identifiers and a pointer pointing to a particular identifier in said sequence of identifiers, wherein said entry is retrieved from said selected forwarding table in response to said particular identifier pointed to by said pointer.

16. The method of claim 14 further comprising the step of modifying said routing context parameter to select a particular forwarding table at each successive node of said sequence of nodes via which said packet is transmitted.

17. A method for transmitting a packet from a source node to a destination node via a sequence of intermediary nodes in a network comprising the steps of:

at the source node, prior to transmission, writing in the packet a sequence of identifiers and a pointer pointing to a particular identifier in said sequence of identifiers,

at one of said intermediary nodes in which said packet is located, selecting a particular forwarding table from a set of forwarding tables maintained in a memory at said one intermediary node,

retrieving an entry from said selected forwarding table at said one intermediary node in response to said particular identifier pointed to by said pointer, and

transmitting said packet to a next node that is indicated by said retrieved entry.

18. The method of claim 17 further comprising at said one intermediary node the step of, in response to said retrieved entry, changing said pointer to a different pointer which points to a different identifier in said sequence of identifiers.

19. The method of claim 18 further comprising the steps of:

receiving said packet at said next node of said sequence of intermediary nodes,

at said next node, selecting a second forwarding table from a second set of forwarding tables maintained in a memory at said next node.

retrieving an entry from said second selected forwarding table in response to said different identifier pointed to by said different pointer, and

transmitting said packet to a further next intermediary node of said sequence of nodes indicated by said entry retrieved from said second selected forwarding table.

20. The method at claim 17 further comprising the step at said source node of writing a routing context parameter in the packet and wherein at said intermediary node said forwarding table is selected in response to said routing context parameter.

21. The method of claim 20 further comprising the step of modifying said routing context parameter to select a particular forwarding table at each successive node of said sequence of intermediary nodes via which said packet is transmitted.

22. A method for transmitting a packet from a source node to a destination node via a sequence of intermediary nodes in a network comprising the steps of:

at the source node, prior to transmission, writing in the packet a sequence of identifiers and a pointer pointing to a particular identifier in said sequence of identifiers,

at one of said intermediary nodes in which said packet is located and where at said one intermediary node a forwarding table is maintained in a memory, retrieving an entry from said forwarding table in response to said particular identifier pointed to by said pointer, and

transmitting said packet to a next node that is indicated by said retrieved entry.

23. The method of claim 22 further comprising at said one intermediary node the step of, in response to said retrieved entry, changing said pointer to a different pointer which points to a different identifier in said sequence of identifiers.

24. The method of claim 23 further comprising the steps of:

receiving said packet at said next node of said sequence of intermediary nodes,

at said next node, selecting a second forwarding table from a second set of forwarding tables maintained in a memory at said next node,

retrieving an entry from said second selected forwarding table in response to said different identifier pointed to by said different pointer, and

transmitting said packet to a further next intermediary node of said sequence of nodes indicated by said entry retrieved from said second selected forwarding table.