System and method for implementing source based and egress based virtual networks in an interconnection network
First Claim
1. An interconnection network, comprising:
- routers interconnected by links;
packets traversing one or more hops across links from packet sources to packet destinations;
subtrees of the routers interconnected by links forming source based virtual networks for each of the packet sources;
subtrees of the routers interconnected by links forming egress based virtual networks for each of the packet destinations; and
a packet traversing a source based virtual network of a packet source, the packet transitioning into an egress based virtual network of a packet destination, the packet traversing the egress based virtual network to the packet destination.
3 Assignments
0 Petitions
Accused Products
Abstract
An interconnection network, particularly a Gamma graph network, comprising a number of interconnected routers implementing source based and egress based virtual networks in order to prevent tree saturation and deadlock while routing packets. The interconnection network can be used as a fabric within a multi-application switch router, for example. Packets traverse the fabric from any packet source to any packet destination by traversing a source based virtual network associated with a packet source and then by traversing an egress based virtual network associated with a packet destination. By partitioning the fabric into source based virtual networks and egress based virtual networks, the number of control structures required to manage them are reduced as compared with destination based virtual network architectures. Furthermore, by dynamically assigning buffer resources to a virtual network when needed provides more efficient utilization of buffer resources as opposed to dedicated assignment of buffer resources to each virtual network.
-
Citations
52 Claims
-
1. An interconnection network, comprising:
-
routers interconnected by links;
packets traversing one or more hops across links from packet sources to packet destinations;
subtrees of the routers interconnected by links forming source based virtual networks for each of the packet sources;
subtrees of the routers interconnected by links forming egress based virtual networks for each of the packet destinations; and
a packet traversing a source based virtual network of a packet source, the packet transitioning into an egress based virtual network of a packet destination, the packet traversing the egress based virtual network to the packet destination. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. An interconnection network, comprising:
-
routers interconnected by links;
packets traversing one or more hops across links from packet sources to packet destinations;
a plurality of source based tunnels fanning out from each packet source over a subtree of routers, each source based tunnel comprises one or more source based tunnel segments, each source based tunnel segment of a source based tunnel is a logical hop across a different link; and
a plurality of egress based tunnels fanning in to each packet destination over a subtree of routers, each egress based tunnel comprises one or more egress based tunnel segments, each egress based tunnel segment of an egress based tunnel is a logical hop across a different link. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27)
-
-
28. An interconnection network, comprising:
-
routers interconnected by links;
packets traversing one or more fabric hops across links from packet sources to packet destinations;
each router comprising a switch coupled to at least one traffic manager, each traffic manager coupled to at least packet source and at least one packet destination, the switch communicating with the traffic manager and one or more routers;
each traffic manager injecting packets from the at least one packet source into source based tunnel segments comprising logical hops across links, each of the source based tunnel segments associated with a packet source and a path to a binding node originating an egress based tunnel to at least one packet destination; and
the switch forwarding packets through source based tunnel segments, the switch forwarding packets through egress based tunnel segments comprising logical hops across links, the egress based tunnel segments corresponding to packet destinations reachable in a number of hops less than the diameter of the interconnection network. - View Dependent Claims (29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39)
-
-
40. A method for preventing tree saturation and deadlock in an interconnection network, comprising:
-
interconnecting routers by links, each router coupled to one or more packet sources and one or more packet destinations;
forming source based virtual networks over subtrees of interconnected routers for each of the packet sources;
forming egress based virtual networks over subtrees of interconnected routers for each of the packet destinations; and
communicating a packet from any packet source to any packet destination by traversing a source based virtual network of a packet source, transitioning into an egress based virtual network of a packet destination, and traversing the egress based virtual network to the packet destination. - View Dependent Claims (41, 42, 43, 44, 45, 46)
-
-
47. A method for preventing tree saturation and deadlock in an interconnection network, comprising:
-
interconnecting routers by links, each router coupled to one or more packet sources and one or more packet destinations;
for each router, implementing a queue within memory for each egress based tunnel segment associated with a packet destination that is reachable from the router in a number of hops less than the diameter of the interconnection network, an egress based tunnel segment is a logical hop across a link associated with a packet destination;
for each router, implementing a queue within memory for each source based tunnel segment associated with a packet source and a path to a binding node that is reachable from the router in a number of hops less than the diameter of the interconnection network, a source based tunnel segment is a logical hop across a link associated with a packet source; and
the total number of queues for source based tunnel segments and egress based tunnel segments at each router being less than the total number of packet destinations of the interconnection network. - View Dependent Claims (48, 49, 50, 51)
-
-
52. An interconnection network, comprising:
-
routers interconnected by links;
packets traversing one or more hops across links from packet sources to packet destinations;
subtrees of the routers interconnected by links forming sets of source based tunnels associated with each of the packet sources;
subtrees of the routers interconnected by links interconnected routers forming sets of egress based tunnels associated with each of the packet destinations;
each router having a means for managing the transmission of packets through each source based tunnel and each egress based tunnel originating from or extending across the router; and
communicating a packet from any packet source to any packet destination by traversing a source based tunnel associated with the packet source, the packet transitioning into an egress based tunnel associated with the packet destination, the packet traversing the egress based virtual network to the packet destination.
-
Specification