Method for inferring physical network topology from end-to-end measurement

• US 8,264,988 B2
• Filed: 01/30/2010
• Issued: 09/11/2012
• Est. Priority Date: 01/30/2009
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Jiang, Guofei, Zhang, Yueping, Ru, Yu
• Primary Examiner(s): Weidner, Timothy J
• Application Number:
  US12/697,237
• Publication Number:
  US 20110058499A1
• Time in Patent Office: 955 Days
• Field of Search: None
• US Class Current: 370/256
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A method for inferring end-to-end network topology and to accurately determine a layer-3 routing tree between one sender and a set of receivers in the presence of anonymous routers in a network.

Claims

1. A computer implemented method for determining a layer-3 topology of a network comprising the steps of:

sending from a single source node a sequence of probing packets to two other receiver nodes wherein each node represents a physical layer-3 device;

determining, based on time-to-live, queuing delay and delay variations between probing packet measurements made at the receiver nodes, two layer-3 routing paths between the source node and the receiver nodes and a node where they diverge;

repeating the above sending and determining steps after changing source-destination pairs such that a number of layer-3 single source routing sub-trees between a source and a number of destination nodes is determined;

merging all the sub-trees into a single routing tree; and

outputting an indication of a network topology which is representative of the network.