Method and apparatus for routing a packet within a plurality of nodes arranged in a line or a tree given a maximum stack depth
First Claim
1. A method for routing a packet within a plurality of n nodes arranged in a line using a stack depth, s, wherein said plurality of n nodes are divided into segments, a first unique label is assigned to each of said segments;
- and within each of said segments, a second unique label is assigned to each node, said method comprising the steps of;
identifying one of said segments based on said first unique label; and
identifying a node within said identified segment based on said second unique label.
8 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus are provided for routing a packet within a plurality of n nodes arranged in a line or tree (or a combination of the foregoing), given a maximum stack depth, s. A fixed stack process for routing packets on a line given a stack depth, s, initially divides a line of n nodes into segments, such as n1/s approximately equal segments. A unique label is assigned to each segment and, within each segment, one of up to n1/s labels is assigned to each node. A fixed stack process for routing packets on a tree, given a target stack depth, s, initially identifies a subset, S, of at nodes from the tree, such as at most 3n1/s nodes, such that after the subset, S, is removed, each remaining subtree has at most n(s-1)/s nodes. A unique label is assigned to each of the nodes in the subset S and, within each remaining subtree, one of up to n(s-1)/s labels is assigned to each node. If the bound on the stack depth cannot be violated, the fixed stack routing process merges every two consecutive levels in the stack to one level.
106 Citations
20 Claims
-
1. A method for routing a packet within a plurality of n nodes arranged in a line using a stack depth, s, wherein said plurality of n nodes are divided into segments, a first unique label is assigned to each of said segments;
- and within each of said segments, a second unique label is assigned to each node, said method comprising the steps of;
identifying one of said segments based on said first unique label; and
identifying a node within said identified segment based on said second unique label. - View Dependent Claims (2, 3, 4, 5, 6)
- and within each of said segments, a second unique label is assigned to each node, said method comprising the steps of;
-
7. A method for routing a packet within a plurality of n nodes arranged in a tree, T, using a stack depth, s, wherein a subset, S, of nodes is identified in said tree, such that after removing said subset, S, of nodes from said tree, each remaining subtree has less than a maximum number of nodes;
- and wherein a first unique label is assigned to each of said nodes in S, and within each of said subtrees, a second unique labels is assigned to each node, said method comprising the steps of;
identifying a node v in said subset, S, using said first unique label;
identifying an edge incident with node v; and
identifying a node within a subtree associated with said edge based on said second unique label. - View Dependent Claims (8, 9, 10, 11, 12, 13)
- and wherein a first unique label is assigned to each of said nodes in S, and within each of said subtrees, a second unique labels is assigned to each node, said method comprising the steps of;
-
14. A system for routing a packet within a plurality of n nodes arranged in a line using a stack depth, s, wherein said plurality of n nodes are divided into segments, a first unique label is assigned to each of said segments;
- and within each of said segments, a second unique label is assigned to each node, said system comprising;
a memory; and
at least one processor, coupled to the memory, operative to;
identify one of said segments based on said first unique label; and
identify a node within said identified segment based on said second unique label. - View Dependent Claims (15, 16, 17)
- and within each of said segments, a second unique label is assigned to each node, said system comprising;
-
18. A system for routing a packet within a plurality of n nodes arranged in a tree, T, using a stack depth, s, wherein a subset, S, of nodes is identified in said tree, such that after removing said subset, S, of nodes from said tree, each remaining subtree has less than a maximum number of nodes;
- and wherein a first unique label is assigned to each of said nodes in S, and within each of said subtrees, a second unique labels is assigned to each node, said system comprising;
a memory; and
at least one processor, coupled to the memory, operative to;
identify a node v in said subset, S, using said first unique label;
identify an edge incident with node v; and
identify a node within a subtree associated with said edge based on said second unique label. - View Dependent Claims (19, 20)
- and wherein a first unique label is assigned to each of said nodes in S, and within each of said subtrees, a second unique labels is assigned to each node, said system comprising;
Specification