专利快速检索-快速检索全球专利，免费商用专利数据库-IPRDB

1. 发明授权

US06347078B1 Multiple path routing 有权
标题翻译：多路径路由
公开(公告)号：US06347078B1
公开(公告)日：2002-02-12
申请号：US09132032
申请日：1998-08-11
申请人： Paolo Narvaez-Guarnieri , Kai-Yeung Siu , Hong-Yi Tzeng
发明人： Paolo Narvaez-Guarnieri , Kai-Yeung Siu , Hong-Yi Tzeng
IPC分类号： H04L1256
CPC分类号： H04L45/00 , H04L45/122 , H04L45/18 , H04L45/22 , H04L45/30
摘要： A novel data structure in a router helps to compute viable next hops for forwarding a data packet from a router to its destination along multiple alternate loop-free paths, which are not necessarily of shortest distance. Each viable next hop may also be specified with a degree of optimality, which enables a route to perform QoS routing and fault-tolerant routing efficiently. The data structure can be implemented as an add-on software to existing routing protocols and may be implemented in existing networks which use shortest path protocols, even where less than all of the routers use the data structure and multiple path scheme described herein.
摘要翻译：路由器中的一种新颖的数据结构有助于计算可行的下一跳，用于将数据包从路由器转发到其目的地，沿着多个不具有最短距离的交替无循环路径。每个可行的下一跳也可以以一定程度的最优性来指定，这使路由能够有效地执行QoS路由和容错路由。数据结构可以作为现有路由协议的附加软件实现，并且可以在使用最短路径协议的现有网络中实现，即使在少于所有路由器使用本文描述的数据结构和多路径方案的情况下也是如此。

2. 发明授权

US06721899B1 Fault-tolerant non-flooding routing 失效
标题翻译：容错非洪泛路由
公开(公告)号：US06721899B1
公开(公告)日：2004-04-13
申请号：US09481100
申请日：2000-01-12
申请人： Paolo Narvaez-Guarnieri , Kai-Yeung Siu , Hong-Yi Tzeng
发明人： Paolo Narvaez-Guarnieri , Kai-Yeung Siu , Hong-Yi Tzeng
IPC分类号： G06F1100
CPC分类号： H04L45/48 , H04L45/02 , H04L45/123 , H04L45/28
摘要： This invention is an algorithm that restores routing in a link-state network after a link failure without flooding the entire routing area with new routing information. The algorithm operates only in the local neighborhood of the failed link and informs the minimum number of routers about the failure.
摘要翻译：本发明是一种在链路故障后恢复链路状态网络中的路由的算法，而不会用新的路由信息淹没整个路由区域。该算法仅在故障链路的本地邻居中运行，并通知路由器关于故障的最小数量。

3. 发明授权

US06704320B1 Dynamic algorithm for determining a shortest path tree between network nodes 失效
标题翻译：用于确定网络节点之间最短路径树的动态算法
公开(公告)号：US06704320B1
公开(公告)日：2004-03-09
申请号：US09275591
申请日：1999-03-24
申请人： Paolo Narvaez , Kai-Yeung Siu , Hong-Yi Tzeng
发明人： Paolo Narvaez , Kai-Yeung Siu , Hong-Yi Tzeng
IPC分类号： H04L1228
CPC分类号： H04L45/02 , H04L45/48
摘要： A dynamic shortest path tree (SPT) algorithm for a router determines a new SPT for a root node in response to a link-state or other network topology change. The dynamic SPT algorithm determines the new SPT as an optimization problem in a linear programming framework based in an existing SPT in the router. The dynamic SPT algorithm emulates maximum decrement of a ball and string model by iteratively selecting nodes of the existing SPT for consideration and update of parent node, child nodes, and distance attributes based on the maximum decrement. For the maximum decrement, a node in the existing SPT is selected by each iteration based on the greatest potential decrease (or least increase) in its distance attribute. The ball and string model that may be employed for the dynamic SPT algorithm represents a network of nodes and links with a ball representing a node and a string representing a link or edge. The length of a string is defined by its link's weight. The set of strings connecting the balls defines a path between the root node and a particular node. The shortest path is the path defined by the strings from a root node to a particular node that are tight. For the dynamic SPT algorithm, an increase (or decrease) in an edge weight in an existing SPT corresponds to a lengthening (or shortening) of a string. By sequentially pulling balls away in a single direction from the ball of the root node, the new SPT becomes defined by the balls and tight strings.
摘要翻译：用于路由器的动态最短路径树（SPT）算法根据链路状态或其他网络拓扑变化确定根节点的新SPT。动态SPT算法将新的SPT确定为基于路由器中现有SPT的线性规划框架中的优化问题。动态SPT算法通过迭代地选择现有SPT的节点来模拟球和串模型的最大减量，以便基于最大减量来考虑和更新父节点，子节点和距离属性。对于最大减量，根据其距离属性中的最大潜在减少（或最小增加），通过每次迭代选择现有SPT中的节点。可用于动态SPT算法的球和弦模型表示节点的网络和与表示节点的球的链接和表示链接或边缘的字符串。字符串的长度由其链接的权重定义。连接球的一组字符串定义了根节点和特定节点之间的路径。最短路径是由根节点到特定节点的字符串定义的路径。对于动态SPT算法，现有SPT中边缘权重的增加（或减小）对应于字符串的延长（或缩短）。通过从根节点的球顺序地将球从单个方向拉出，新的SPT由球和紧密的弦组成。

4. 发明授权

US6098107A Dynamic algorithms for shortest path tree computation 失效
标题翻译：用于最短路径树计算的动态算法
公开(公告)号：US6098107A
公开(公告)日：2000-08-01
申请号：US961736
申请日：1997-10-31
申请人： Paolo Narvaez-Guarnieri , Hong-Yi Tzeng
发明人： Paolo Narvaez-Guarnieri , Hong-Yi Tzeng
IPC分类号： H04L12/56 , G06F15/173
CPC分类号： H04L45/02 , H04L45/48
摘要： Method for computing a shortest path tree structure for nodes in an interconnected network comprising the steps of maintaining a data structure T consisting of a set of edges e interconnecting the plurality of nodes in the network, each node having an associated parent node and distance value attributes; determining a weight change .DELTA. of an edge; obtaining a set of candidate nodes having associated parent and distance attributes that are affected by the weight change; selecting a node of the set of candidate nodes; identifying one or more descendents of the selected node and calculating a new distance attribute for each of the one or more descendents; searching for other nodes connected to the one or more identified descendent nodes and determining whether they should be included in the data structure T; and, repeating the selecting, identifying, calculating, searching and determining steps until all nodes of the set of candidate nodes are selected to update the data structure T.
摘要翻译：用于计算互连网络中的节点的最短路径树结构的方法，包括以下步骤：维护由网络中的多个节点互连的一组边缘组成的数据结构T，每个节点具有相关联的父节点和距离值属性 ; 确定边缘的重量变化DELTA; 获得具有受重量变化影响的相关联的父和距离属性的一组候选节点; 选择所述候选节点集合中的节点; 识别所选节点的一个或多个后代，并为所述一个或多个后代中的每一个计算新的距离属性; 搜索连接到一个或多个识别的后代节点的其他节点并确定它们是否应被包括在数据结构T中; 并且重复选择，识别，计算，搜索和确定步骤，直到选择候选节点集合中的所有节点来更新数据结构T.

5. 发明授权

US6067574A High speed routing using compressed tree process 失效
标题翻译：使用压缩树进程的高速路由
公开(公告)号：US6067574A
公开(公告)日：2000-05-23
申请号：US80557
申请日：1998-05-18
申请人： Hong-Yi Tzeng
发明人： Hong-Yi Tzeng
IPC分类号： G06F15/173 , G06T9/40 , G60F15/16
CPC分类号： G06F15/17337 , G06T9/40 , Y10S707/99942
摘要： A router uses the destination address of its incoming packets to decide the proper outgoing interfaces by searching among all of the stored prefixes for the prefix which has the longest match when compared to the destination address in the packet. Prefix trees are employed to represent the set of prefixes to be searched and high-speed, longest prefix matches are performed. An efficient data structure compresses any prefix tree structure so that the number of memory accesses needed to find the longest prefix for any address depends only on the length of the prefix rather than on the number of stored prefixes. Illustratively, only four, 64-bit memory accesses are required to find the longest prefix match for each IPv4 address in the worst case, while only 3 Mbytes are required to store a 128K-entry routing table.
摘要翻译：路由器使用其输入分组的目的地地址来确定正确的出站接口，通过在与分组中的目的地地址相比较时具有最长匹配的前缀的所有存储的前缀中搜索。前缀树用于表示要搜索的前缀集，并执行高速，最长的前缀匹配。有效的数据结构压缩任何前缀树结构，以便为任何地址找到最长前缀所需的存储器访问数量仅取决于前缀的长度，而不是依赖于存储的前缀的数量。说明性的是，在最坏的情况下，只需要四个64位的存储器访问来找到每个IPv4地址的最长前缀匹配，而只需要3M字节来存储一个128K入口路由表。

6. 发明授权

US06959323B1 Scalable atomic multicast 有权
标题翻译：可扩展的原子组播
公开(公告)号：US06959323B1
公开(公告)日：2005-10-25
申请号：US09384699
申请日：1999-08-27
申请人： Hong-Yi Tzeng , Yin Zhang
发明人： Hong-Yi Tzeng , Yin Zhang
IPC分类号： G06F15/16 , G06F15/173 , H04L12/18 , H04L12/56 , H04L29/08
CPC分类号： H04L12/1881 , H04L47/10 , H04L47/15 , H04L47/34 , H04L67/02
摘要： This document describes a protocol for reliably synchronizing states of nodes in a distributed environment through use of a Scalable Atomic Multicast (SAM) Service that ensures both atomicity and total order among messages sent to a multicast group. In addition to possessing good scalability property, this fault-tolerant protocol does not require explicit knowledge of multicast group membership, allows for non-disturbing state synchronization, and supports asynchronous non-blocking communications. According to one aspect of this invention, a dedicated sequencer is responsible solely for assigning sequence numbers to the multicast messages. The sequencer does not multicast the messages. Another aspect of the invention is the use of receiver-driven negative acknowledgments. According to third aspect, the invention supports message consolidation and garbage collection.
摘要翻译：本文档描述了一种通过使用可扩展原子组播（SAM）服务可靠地同步分布式环境中的节点状态的协议，该可扩展原子组播（SAM）服务确保发送到多播组的消息的原子性和总顺序。除了具有良好的可扩展性，该容错协议不需要对组播组成员资格的明确知识，允许非干扰状态同步，并支持异步非阻塞通信。根据本发明的一个方面，专用定序器仅用于为多播消息分配序列号。定序器不会组播消息。本发明的另一方面是使用接收机驱动的否定确认。根据第三方面，本发明支持消息合并和垃圾收集。

7. 发明授权

US6061712A Method for IP routing table look-up 失效
标题翻译： IP路由表查找方法
公开(公告)号：US6061712A
公开(公告)日：2000-05-09
申请号：US3767
申请日：1998-01-07
申请人： Hong-Yi Tzeng
发明人： Hong-Yi Tzeng
IPC分类号： H04L12/701 , H04L12/741 , H04L12/743 , G06F15/16
CPC分类号： H04L45/00 , H04L45/54 , H04L45/7457
摘要： A high speed router employs a hashed radix tree method for IP route look-up operations. The first k bits of an X bit IP address are hashed and used as an index to a RAM whose output is a pointer to the root node of one of a plurality of radix trees. Taking into account the subnet mask of the IP address, each of the radix trees examines the significant bits of the remaining X-k bits of the IP address for a match. Each match is stored in memory at least until a better match is found. If a best match is found a pointer to a second RAM is emitted, whose output is the best route. The tree can be constructed such that one or more bits can be examined simultaneously at each level. To gain the benefit of examining multiple bits at each level and minimize the required memory, a perfect hashing method is employed to eliminate unnecessary nodes in each tree.
摘要翻译：高速路由器采用散列基数树法进行IP路由查找操作。 X位IP地址的前k位被散列并用作RAM的索引，RAM的输出是指向多个基数之一的根节点的指针。考虑到IP地址的子网掩码，每个基数树检查匹配的IP地址的剩余X-k位的有效位。每个匹配至少存储在内存中，直到找到更好的匹配。如果找到最佳匹配，则发出指向第二RAM的指针，其输出是最佳路由。可以构造树，使得可以在每个级别同时检查一个或多个比特。为了获得在每个级别检查多个比特并最小化所需存储器的好处，采用完美的哈希方法来消除每个树中的不必要的节点。

8. 发明授权

US06006272A Method for network address translation 失效
标题翻译：网络地址转换方法
公开(公告)号：US06006272A
公开(公告)日：1999-12-21
申请号：US27708
申请日：1998-02-23
申请人： Murali Aravamudan , Hong-Yi Tzeng
发明人： Murali Aravamudan , Hong-Yi Tzeng
IPC分类号： H04L29/12 , H04L12/66
CPC分类号： H04L61/6022 , H04L29/12009 , H04L29/12367 , H04L29/12377 , H04L29/12452 , H04L29/12584 , H04L29/12839 , H04L61/2514 , H04L61/2517 , H04L61/2546 , H04L61/2596
摘要： A method for translating non internet unique addresses of a home network device to an internet unique address for internet communication through a router. Every device within a given home network is assigned three addresses:(i) a configured address identical to the network address of the router enabling access to an Internet; (ii) a logical address visible only to the other devices in the same home network; and (iii) a medium access control ("MAC") address. Every packet originating from a home network source device includes its MAC address, the router MAC address, its configured address and the network destination address, and is forwarded to its destination through the router. The router examines the network destination address to determine whether the communication is intranet or internet. For intranet communications the router replaces the configured address of the home network source device with the logical address of the home network source device, the logical address of the home network destination device with the configured address, its MAC address with the MAC address of the home network destination device, and forwards the packet to the home network destination device. For Internet communications the router forwards the packet along the Internet without replacing any of the source or destination information in the headers of the packet. Based on the source MAC address, however, the router records the logical address of the home network source device as well as the DA, SP, DP and PT in order to identify a response to the packet from the Internet destination device.
摘要翻译：用于将家庭网络设备的非互联网唯一地址转换为互联网唯一地址以通过路由器进行互联网通信的方法。给定家庭网络中的每个设备都分配三个地址：（i）与允许访问互联网的路由器的网络地址相同的配置地址; （ii）仅在同一家庭网络中对其他设备可见的逻辑地址; 和（iii）介质访问控制（“MAC”）地址。源自家庭网络源设备的每个包包括其MAC地址，路由器MAC地址，其配置的地址和网络目的地址，并通过路由器转发到其目的地。路由器检查网络目的地址，以确定通信是内联网还是互联网。对于内部网通信，路由器将家庭网络源设备的配置地址替换为家庭网络源设备的逻辑地址，具有配置地址的家庭网络目的地设备的逻辑地址，其MAC地址与家庭MAC地址网络目的地设备，并将分组转发到家庭网络目的地设备。对于因特网通信，路由器沿着因特网转发数据包，而不需要替换数据包头中的任何源或目标信息。然而，基于源MAC地址，路由器记录家庭网络源设备的逻辑地址以及DA，SP，DP和PT，以便识别来自因特网目的地设备的分组的响应。

9. 发明授权

US07466703B1 Scalable high speed router apparatus 有权
标题翻译：可扩展的高速路由器设备
公开(公告)号：US07466703B1
公开(公告)日：2008-12-16
申请号：US09303718
申请日：1999-04-30
申请人： Raman Arunachalam , Vijay P Kumar , Sunder R Rathnavelu , Dimitrios Stiliadis , Hong-Yi Tzeng
发明人： Raman Arunachalam , Vijay P Kumar , Sunder R Rathnavelu , Dimitrios Stiliadis , Hong-Yi Tzeng
IPC分类号： H04L12/28
CPC分类号： H04L45/00 , H04L45/60 , H04L45/64 , H04L49/201 , H04L49/254 , H04L49/3009
摘要： A scalable, high-speed router for routing packets of information through an interconnected network comprises an interface for receiving a packet containing header and data information; a device for extracting routing information from the header of an arrived packet and generating a corresponding header packet for the arrived packet; a memory device for storing the data information of the arrived packet at predetermined memory locations; a device for processing the corresponding header packet to determine a route for the arrived packet and assigning packet forwarding information to the header packet; and, a device for retrieving the data information from the predetermined memory locations and forwarding both the data and header packet containing the packet forwarding information to the interface for routing the packet to a further destination in accordance with the packet forwarding information. The processing device includes devices performing filtering, route-table lookup and flow identification functions and which devices are organized in a pipelined fashion for successive, high-speed operations on the header packet. The router ensures that the arrived packet is forwarded in accordance with any quality of service requirements and flow specifications.
摘要翻译：用于通过互连网络路由信息包的可扩展的高速路由器包括用于接收包含报头和数据信息的分组的接口; 从到达分组的头部提取路由信息的装置，并生成用于所述到达分组的对应的报头分组; 存储装置，用于将预定分组的数据信息存储在预定的存储位置; 用于处理对应的报头分组以确定所述到达分组的路由并将分组转发信息分配给所述报头分组的设备; 以及用于从预定存储器位置检索数据信息的装置，并且将包含分组转发信息的数据和报头分组转发到接口，用于根据分组转发信息将分组路由到另外的目的地。处理设备包括执行过滤，路由表查找和流识别功能的设备，并且哪些设备以流水线方式组织，用于对报头分组进行连续的高速操作。路由器确保到达的数据包根据任何服务质量要求和流量规范进行转发。

10. 发明授权

US06515965B1 Available bit rate flow control for service allocation in a packet network 有权
标题翻译：分组网络中业务分配的可用比特流量控制
公开(公告)号：US06515965B1
公开(公告)日：2003-02-04
申请号：US09277396
申请日：1999-03-26
申请人： Yiwei T. Hou , Shivendra S. Panwar , Hong-Yi Tzeng
发明人： Yiwei T. Hou , Shivendra S. Panwar , Hong-Yi Tzeng
IPC分类号： G01R3108
CPC分类号： H04L47/822 , H04L47/10 , H04L47/15 , H04L47/70 , H04L47/762 , H04L47/781 , H04L47/783 , H04L2012/5635 , H04L2012/5636 , H04Q11/0478
摘要： A packet network employs flow control providing assigned rates to sessions in accordance with a general max-min (GMM) rate allocation. The GMM rate allocation accounts for the minimum cell rate and peak cell rate requirements for each session. For one case, a centralized flow control algorithm is employed that sorts sessions based on increasing minimum cell rate. The centralized flow control algorithm employs an iterative process of increasing the rate of the smallest rate session and adding sessions to the process when the smallest rate session equals the next higher rate session. The rates are increased until the rate either reaches the peak cell rate of the session or the link saturates. For a second case, a distributed flow control algorithm is employed with a distributed protocol within the network to allocate capacity of network links to sessions. For the distributed flow control algorithm, an iterative process of rate allocation uses a modified version of the Consistent Marking method. In the modified version of the Consistent Marking method, a saturated link only marks those sessions reaching a corresponding GMM-bottleneck link rate on links elsewhere in the network. The session traversing its own GMM-bottleneck link is not marked.
摘要翻译：分组网络采用流量控制，根据一般的最大最小（GMM）速率分配向会话提供分配的速率。 GMM速率分配占每个会话的最小信元速率和峰值信元速率要求。对于一种情况，采用集中流量控制算法，其基于增加的最小信元速率对会话进行排序。集中式流量控制算法采用迭代过程，当最小速率会话等于下一个较高速率会话时，增加最小速率会话的速率并向进程添加会话。速率增加，直到速率达到会话的峰值信元速率或链路饱和。对于第二种情况，使用分布式流控制算法与网络内的分布式协议来分配网络链路到会话的容量。对于分布式流量控制算法，速率分配的迭代过程使用一致性标记方法的修改版本。在一致性标记方法的修改版本中，饱和链接仅标记那些在网络其他地方的链路达到相应GMM瓶颈链路速率的会话。遍历其自己的GMM瓶颈链接的会话未标记。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式