公开(公告)号：US08284788B2

公开(公告)日：2012-10-09

申请号：US12512693

申请日：2009-07-30

申请人： Cedric Westphal ,  Guanhong Pei

发明人： Cedric Westphal ,  Guanhong Pei

IPC分类号： H04L12/28 ,  H04L12/56

CPC分类号： H04L45/48 ,  H04L45/02 ,  H04L45/122 ,  H04L45/126 ,  H04L45/14 ,  H04L45/54

摘要： A method and apparatus is disclosed herein for scalable routing with greedy embedding. In one embodiment, the method comprises storing log(n) coordinates in a routing table, where n is the number of nodes in a network, and further wherein the log(n) coordinates are generated by constructing a greedy embedding that embeds a graph topology depicting connections between n nodes of a network into a geometric space so as to use greedy forwarding by generating a spanning tree out of a connection graph representing the connections between the n nodes of the network, decomposing the tree into at most n branches, assigning a set of geometric coordinates to vertices in the tree in an n-dimensional space, and projecting the set of geometric coordinates onto a k-dimensional space, where k is less than n, to create the log(n) coordinates; and routing packets via nodes of the network using the log(n) coordinates in the routing table.

摘要翻译： 本文公开了一种用于具有贪心嵌入的可扩展路由的方法和装置。 在一个实施例中，该方法包括在路由表中存储log（n）坐标，其中n是网络中的节点数，并且其中log（n）坐标是通过构建嵌入图形拓扑的贪心嵌入来生成的 描绘网络的n个节点之间的连接到几何空间，以便通过从表示网络的n个节点之间的连接的连接图中生成生成树来使用贪婪转发，将树分解为最多n个分支，分配 将几何坐标集合在n维空间中的树中的顶点，并将几何坐标集合投影到k维空间上，其中k小于n，以创建log（n）坐标; 并使用路由表中的log（n）坐标来路由节点的网络路由数据包。

公开(公告)号：US20100290480A1

公开(公告)日：2010-11-18

申请号：US12512693

申请日：2009-07-30

申请人： Cedric Westphal ,  Guanhong Pei

发明人： Cedric Westphal ,  Guanhong Pei

IPC分类号： H04L12/28

CPC分类号： H04L45/48 ,  H04L45/02 ,  H04L45/122 ,  H04L45/126 ,  H04L45/14 ,  H04L45/54

摘要： A method and apparatus is disclosed herein for scalable routing with greedy embedding. In one embodiment, the method comprises storing log(n) coordinates in a routing table, where n is the number of nodes in a network, and further wherein the log(n) coordinates are generated by constructing a greedy embedding that embeds a graph topology depicting connections between n nodes of a network into a geometric space so as to use greedy forwarding by generating a spanning tree out of a connection graph representing the connections between the n nodes of the network, decomposing the tree into at most n branches, assigning a set of geometric coordinates to vertices in the tree in an n-dimensional space, and projecting the set of geometric coordinates onto a k-dimensional space, where k is less than n, to create the log(n) coordinates; and routing packets via nodes of the network using the log(n) coordinates in the routing table.

摘要翻译： 本文公开了一种用于具有贪心嵌入的可扩展路由的方法和装置。 在一个实施例中，该方法包括在路由表中存储log（n）坐标，其中n是网络中的节点数，并且其中log（n）坐标是通过构建嵌入图形拓扑的贪心嵌入来生成的 描绘网络的n个节点之间的连接到几何空间，以便通过从表示网络的n个节点之间的连接的连接图中生成生成树来使用贪婪转发，将树分解为最多n个分支，分配 将几何坐标集合在n维空间中的树中的顶点，并将几何坐标集合投影到k维空间上，其中k小于n，以创建log（n）坐标; 并使用路由表中的log（n）坐标来路由节点的网络路由数据包。