Invention Grant
US07656857B2 Directed acyclic graph computation by orienting shortest path links and alternate path links obtained from shortest path computation
有权
通过定向从最短路径计算获得的最短路径链路和备用路径链路的定向非循环图计算
- Patent Title: Directed acyclic graph computation by orienting shortest path links and alternate path links obtained from shortest path computation
- Patent Title (中): 通过定向从最短路径计算获得的最短路径链路和备用路径链路的定向非循环图计算
-
Application No.: US11251765Application Date: 2005-10-18
-
Publication No.: US07656857B2Publication Date: 2010-02-02
- Inventor: Pascal Thubert , Eric M. Levy-Abegnoli
- Applicant: Pascal Thubert , Eric M. Levy-Abegnoli
- Applicant Address: US CA San Jose
- Assignee: Cisco Technology, Inc.
- Current Assignee: Cisco Technology, Inc.
- Current Assignee Address: US CA San Jose
- Agent Leon R. Turkevich
- Main IPC: H04L12/28
- IPC: H04L12/28

Abstract:
Each network node in a network is configured for calculating a directed acyclic graph that provides at least one path from all the other network nodes toward the one network node. The network node performs a modified shortest path first calculation by identifying next-hop nodes adjacent to the network node, and orienting the link of each next-hop node toward itself (i.e., the origin). The network node also identifies secondary adjacent nodes, adjacent to each of the next hop nodes, and extends paths from next-hop nodes to the associated secondary adjacent nodes while orienting each of the links of the path between adjacent nodes and next-hop nodes toward the next hop nodes. The paths of the nodes form a directed acyclic graph from any other network node toward the origin, enabling distribution of the directed acyclic graph to the other network nodes for optimized reachability to the network node.
Public/Granted literature
Information query