首页>
外国专利>
Method and apparatus for routing a packet within a plurality of nodes arranged in a line or a tree given a maximum stack depth
Method and apparatus for routing a packet within a plurality of nodes arranged in a line or a tree given a maximum stack depth
展开▼
机译：在给定最大堆栈深度的情况下，用于在排列成行或树的多个节点内路由数据包的方法和装置
展开▼
页面导航
摘要
著录项
相似文献
摘要
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 3 n1/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.
展开▼
机译：提供了一种方法和装置，用于在给定最大堆栈深度s的情况下，在以行或树（或前述的组合）排列的多个n个节点内路由分组。用于在给定堆栈深度s的行上路由数据包的固定堆栈过程最初会将n个节点的行划分为段，例如n 1 / s 近似相等的段。唯一标签分配给每个段，并且在每个段内，最多n 1 / s 个标签之一分配给每个节点。在给定目标堆栈深度s的情况下，用于在树上路由数据包的固定堆栈过程最初会标识树中at节点的子集S，例如最多3 n 1 / s 个节点，这样在子集S被删除之后，每个剩余的子树最多具有n （s-1）/ s 个节点。唯一标签分配给子集S中的每个节点，并且在每个其余子树中，最多n （s-1）/ s 个标签之一分配给每个节点。如果不能违反堆栈深度的界限，则固定堆栈路由过程会将堆栈中每两个连续的级别合并为一个级别。
展开▼
