Multiplex communications – Diagnostic testing
Reexamination Certificate
2000-07-12
2004-04-27
Ngo, Ricky (Department: 2662)
Multiplex communications
Diagnostic testing
C370S250000, C370S254000, C709S224000
Reexamination Certificate
active
06728214
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to testing of network routers, particularly for compliance with Internet routing protocols.
2. Discussion of the Known Art
The Internet is a packet-switched network that enables linked host computers to exchange information in the form of packets. When information packets are transmitted from a source node to a destination node via the network, routing decisions are made by special purpose computers called Internet protocol (IP) routers. The routers are connected using a variety of linking media including, e.g., telephone lines, Ethernet segments, satellite links, ATM and FDDI.
To route packets correctly and efficiently, routers must follow a set of rules known as routing protocols. See C. Huitema, Routing in the Internet, Prentice-Hall (1995). Typical protocols used for Internet traffic include Routing Information Protocol (RIP) Open Shortest Path First (OSPF) and Border Gateway Protocol (BGP). See C. Hedrick, RFC 1058, the Internet Engineering Task Force (June 1988); J. T. Moy, OSPF—Anatomy of an Internet Routing Protocol, Addison-Wesley (1998); and Y. Rekhter, et al., RFC 1771, Internet Engineering Task Force (March 1995). While there are no precise specifications for these routing protocols, there are commonly expected invariant behaviors for routers such as (1) compiling a correct routing table, (2) proper packet forwarding, and (3) accumulating correct network topology information. Thus, it is important to test whether or not a given router will operate as expected in a network where it is to be deployed.
Internet usage is increasing rapidly. Sophisticated functions and services, such as service differentiation, quality-of-service (QoS) routing, multi casting, and World Wide Web are introduced on a regular basis. Because the design and implementation of routing protocols in such an environment are complex, proper testing of routers to be used on the Internet under a given protocol, is indispensable.
Typical systems and tools for detecting IP router faults, may be classified either as passive monitoring tools or as active testing tools. An approach used by most monitoring tools such as “RouteMonitor” works as follows. A collection of monitoring devices are deployed in an existing network to observe traffic exchanged between network routers. The devices are passive in that they do not inject route updates into the network. Based on observed routing information, the devices imitate the operation of a real router, execute a given routing protocol, and compute a routing table. Faults are then found by comparing the computed routing tables with an analysis of statistics for each route in the routing table. See D. Massey, et al, Fault Detection in Routing Protocols, Proceeding of International Conference on Network Protocols, pages 31-40 (1999).
Active testing is more effective for fault detection. Available commercial tools include Qosnetics QA Robot and Midnight ANVIL. See Qosnetics, QA robot, (now Agilent Technologies, Inc., Palo Alto, Calif.) (2000); and Midnight Networks, Anvil, (now Empirix, Waltham, Mass.). These tools generate a set of tests for “typical” network configurations or topologies. Because it is not feasible computationally to consider all possible network configurations, existing tools consider only a small subset of possible configurations. Moreover, this subset is chosen in an ad-hoc manner. Thus, even if a router passes all tests using a current tool, there remains a lack of statistical confidence in any judgment rendered by the tool.
SUMMARY OF THE INVENTION
According to the invention, a method of testing a network router for operation according to a given protocol, includes coupling a router under test (RUT) to a test host device, and configuring the device to simulate a network having at most a given number of router nodes and at most a given number of network nodes with edges connecting the router and the network nodes to one another. The host device sends information packets to and receives information packets from the RUT for each of a number of test network topologies under the given protocol. Each test network topology is determined by inserting or deleting an edge or a node to or from a prior test network topology in a probabilistic manner. Operation of the RUT is evaluated with respect to at least one of routing table compilation, packet forwarding, and network topology information accumulated by the RUT. A judgment concerning operation of the RUT under the given protocol is then rendered.
REFERENCES:
patent: 5867689 (1999-02-01), McLain, Jr.
patent: 6243357 (2001-06-01), Sasagawa
patent: 6408335 (2002-06-01), Schwaller et al.
patent: 6442141 (2002-08-01), Borella et al.
patent: 6442615 (2002-08-01), Nordenstam et al.
patent: 6483811 (2002-11-01), Jabbarnezhad
patent: 6584073 (2003-06-01), Steele et al.
patent: 411163916 (1999-06-01), None
Rexford et al, “PP-MESS-SIM: A Simulator for Evaluationg Multicomputer Interconnection Neworks”, Apr. 1995, pp 84-93.*
D. Massey et al, Fault Detection in Routing Protocols, Proc. of Tnt'l Conf. on Network Protocols, 31-40 (1999).
D. Lee, et al, Principles and Methods of Testing Finite State Machines—a Survey, Proc. IEEE, Aug. 1996 at 1089-1123.
J. T. Moy, OSPF Anatomy of an Internet Routing Protocol Addison-Wesley (1998) at 3-25.
Hao Ruibing
Lee David
Sinha Rakesh Kumar
Vlah Dario
Lucent Technologies - Inc.
Ngo Ricky
Nguyen Alan V.
LandOfFree
Testing of network routers under given routing protocols does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Testing of network routers under given routing protocols, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Testing of network routers under given routing protocols will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3242011