INTER-DOMAIN ROUTING IN AN N-ARY-TREE AND SOURCE-ROUTING BASED COMMUNICATION FRAMEWORK

• US 20120106560A1
• Filed: 09/27/2011
• Published: 05/03/2012
• Est. Priority Date: 11/01/2010
• Status: Active Grant

• Current Assignee: Indian Institute of Technology Bombay
• Original Assignee: Indian Institute of Technology Bombay
• Inventors: Gumaste, Ashwin
• Granted Patent: US 8,792,506 B2
• Time in Patent Office: Days
• US Class Current: 370/401
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

Systems and techniques for processing and forwarding packets are described. Specifically, some embodiments can include a receiving mechanism, a determining mechanism, a generating mechanism, and a sending mechanism. The receiving mechanism can be configured to receive a first packet that is to be routed from a first node in a first Autonomous System (AS) to a second node in a second AS. The determining mechanism can be configured to determine a set of bits that encodes a route in an n-ary tree that includes the first node and a root node in the first AS. The generating mechanism can be configured to generate, based on the first packet, a second packet that includes the set of bits and an identifier associated with the second AS. The sending mechanism can be configured to send the second packet.

Claims

1. An apparatus, comprising:

a receiving mechanism configured to receive a first packet that is to be routed from a first node in a first Autonomous System (AS) to a second node in a second AS;

a determining mechanism configured to determine a set of bits that encodes a route in an n-ary tree that includes the first node and a root node in the first AS;

a generating mechanism configured to generate, based on the first packet, a second packet that includes the set of bits and an identifier associated with the second AS; and

a sending mechanism configured to send the second packet to the root node in the first AS.

2. The apparatus of claim 1, wherein the packet is an Ethernet packet, and wherein the set of bits are stored in one or more VLAN (Virtual Local Area Network) tags.

3. The apparatus of claim 1, wherein the packet is an MPLS (Multi-Protocol Label Switching) packet, and wherein the set of bits are stored in one or more MPLS labels.

4. The apparatus of claim 1, wherein the route in the n-ary tree corresponds to a shortest path in the n-ary tree from the first node to the root node in the first AS.

5. The apparatus of claim 1, wherein the second packet causes the root node in the first AS to generate a third packet based on the second packet, and send the third packet to a root node in the second AS.

6. The apparatus of claim 5, wherein the third packet causes the root node in the second AS to generate a fourth packet based on the third packet, and send the fourth packet to the second node in the second AS.

7. An apparatus, comprising:

a processor; and

a non-transitory storage medium storing instructions that are capable of being executed by the processor, the instructions comprising;

instructions to receive a first packet that is to be routed from a first node in a first Autonomous System (AS) to a second node in a second AS;

instructions to determine a set of bits that encodes a route in an n-ary tree that includes the first node and a root node in the first AS;

instructions to generate, based on the first packet, a second packet that includes the set of bits and an identifier associated with the second AS; and

instructions to send the second packet to the root node in the first AS.

8. The apparatus of claim 7, wherein the packet is an Ethernet packet, and wherein the set of bits are stored in one or more VLAN (Virtual Local Area Network) tags.

9. The apparatus of claim 7, wherein the packet is an MPLS (Multi-Protocol Label Switching) packet, and wherein the set of bits are stored in one or more MPLS labels.

10. The apparatus of claim 7, wherein the route in the n-ary tree corresponds to a shortest path in the n-ary tree from the first node to the root node in the first AS.

11. The apparatus of claim 7, wherein the second packet causes the root node in the first AS to generate a third packet based on the second packet, and send the third packet to a root node in the second AS.

12. The apparatus of claim 11, wherein the third packet causes the root node in the second AS to generate a fourth packet based on the third packet, and send the fourth packet to the second node in the second AS.

13. A method, comprising:

receiving a first packet that is to be routed from a first node in a first Autonomous System (AS) to a second node in a second AS;

determining a set of bits that encodes a route in an n-ary tree that includes the first node and a root node in the first AS;

generating, based on the first packet, a second packet that includes the set of bits and an identifier associated with the second AS; and

sending the second packet to the root node in the first AS.

14. The method of claim 13, wherein the packet is an Ethernet packet, and wherein the set of bits are stored in one or more VLAN (Virtual Local Area Network) tags.

15. The method of claim 13, wherein the packet is an MPLS (Multi-Protocol Label Switching) packet, and wherein the set of bits are stored in one or more MPLS labels.

16. The method of claim 13, wherein the route in the n-ary tree corresponds to a shortest path in the n-ary tree from the first node to the root node in the first AS.

17. The method of claim 13, wherein the second packet causes the root node in the first AS to generate a third packet based on the second packet, and send the third packet to a root node in the second AS.

18. The method of claim 17, wherein the third packet causes the root node in the second AS to generate a fourth packet based on the third packet, and send the fourth packet to the second node in the second AS.

19. A method, comprising:

receiving a first packet that is to be routed from a first node to a second node in a network;

determining a set of bits that encodes a route in a binary tree/graph that is embedded in the network, wherein the route in the binary tree/graph corresponds to a preselected path in the network from the first node to the second node;

generating, based on the first packet, a second packet that includes the set of bits; and

sending the second packet to the second node.

20. The method of claim 19, wherein the preselected path is a shortest path from the first node to the second node.

21. The method of claim 19, wherein the packet is an Ethernet packet, and wherein the set of bits are stored in one or more VLAN (Virtual Local Area Network) tags.

22. The method of claim 19, wherein the packet is an MPLS (Multi-Protocol Label Switching) packet, and wherein the set of bits are stored in one or more MPLS labels.