CN1153417C - Simulation method and system for priority protocal of Internet large-scale route to open shortest path - Google Patents
Simulation method and system for priority protocal of Internet large-scale route to open shortest path Download PDFInfo
- Publication number
- CN1153417C CN1153417C CNB02146040XA CN02146040A CN1153417C CN 1153417 C CN1153417 C CN 1153417C CN B02146040X A CNB02146040X A CN B02146040XA CN 02146040 A CN02146040 A CN 02146040A CN 1153417 C CN1153417 C CN 1153417C
- Authority
- CN
- China
- Prior art keywords
- router
- subsystem
- test
- break
- protocol
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 title claims abstract description 17
- 238000004088 simulation Methods 0.000 title abstract description 15
- 238000012360 testing method Methods 0.000 claims abstract description 107
- 238000011161 development Methods 0.000 claims abstract description 5
- 238000010998 test method Methods 0.000 claims description 9
- 230000008569 process Effects 0.000 claims description 8
- 230000002452 interceptive effect Effects 0.000 claims description 4
- 238000013507 mapping Methods 0.000 claims description 3
- 238000010586 diagram Methods 0.000 description 20
- 238000011160 research Methods 0.000 description 8
- 238000004422 calculation algorithm Methods 0.000 description 7
- 238000005516 engineering process Methods 0.000 description 7
- 238000002474 experimental method Methods 0.000 description 7
- 238000004458 analytical method Methods 0.000 description 6
- 230000006870 function Effects 0.000 description 5
- 238000013461 design Methods 0.000 description 3
- 230000003993 interaction Effects 0.000 description 3
- 238000005259 measurement Methods 0.000 description 3
- 238000012545 processing Methods 0.000 description 3
- 230000004044 response Effects 0.000 description 3
- 238000013517 stratification Methods 0.000 description 3
- RTZKZFJDLAIYFH-UHFFFAOYSA-N Diethyl ether Chemical compound CCOCC RTZKZFJDLAIYFH-UHFFFAOYSA-N 0.000 description 2
- 230000005540 biological transmission Effects 0.000 description 2
- 230000003111 delayed effect Effects 0.000 description 2
- 230000002776 aggregation Effects 0.000 description 1
- 238000004220 aggregation Methods 0.000 description 1
- 238000013459 approach Methods 0.000 description 1
- 238000004364 calculation method Methods 0.000 description 1
- 238000006243 chemical reaction Methods 0.000 description 1
- 238000012790 confirmation Methods 0.000 description 1
- 238000010168 coupling process Methods 0.000 description 1
- 238000005859 coupling reaction Methods 0.000 description 1
- 230000003247 decreasing effect Effects 0.000 description 1
- 230000001934 delay Effects 0.000 description 1
- 230000001066 destructive effect Effects 0.000 description 1
- 230000007613 environmental effect Effects 0.000 description 1
- 238000011156 evaluation Methods 0.000 description 1
- 238000013213 extrapolation Methods 0.000 description 1
- 238000002347 injection Methods 0.000 description 1
- 239000007924 injection Substances 0.000 description 1
- 239000000463 material Substances 0.000 description 1
- 238000005457 optimization Methods 0.000 description 1
- RLLPVAHGXHCWKJ-UHFFFAOYSA-N permethrin Chemical compound CC1(C)C(C=C(Cl)Cl)C1C(=O)OCC1=CC=CC(OC=2C=CC=CC=2)=C1 RLLPVAHGXHCWKJ-UHFFFAOYSA-N 0.000 description 1
- 238000004451 qualitative analysis Methods 0.000 description 1
- 238000004445 quantitative analysis Methods 0.000 description 1
- 238000013179 statistical model Methods 0.000 description 1
- 230000001360 synchronised effect Effects 0.000 description 1
- 239000002699 waste material Substances 0.000 description 1
Images
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The present invention relates to a simulation method and a system for priority protocols of Internet large-scale routes to open shortest paths, which belongs to the technical field of Internet large-scale routes. The present invention is characterized in that the system takes a distributed real-time operation system as a development platform, combines route protocol emulation and Internet topological structure emulation and is used for testing the route protocols. The system firstly simulates a topological structure which is similar to an actual network according to a tested router, and a proper node can be found in the topological structure so as to represent the tested router according to actual application requirements of the tested router. The simulation system simulates all other nodes so as to exchange route information with the tested router, and the tested router can carry out route protocol tests in simulated large-scale network environment. The system makes use of a penetration-terminal network topology model to map the Internet topological structure. Compared with the prior art, the present invention can provide a complete Internet large-scale route emulation function.
Description
Technical field
Routing Protocol method of testing and system based on break-through-terminal network model belong to extensive route technology field, the Internet, relate in particular to a kind of Routing Protocol realization and internet topological structure simulation and the extensive mutual measuring technology of route.
Background technology
Route technology is the core of Internet, about the research work of route aspect is based upon on the basis of theory analysis and simulated experiment usually.For example, Sidhu etc. are by simulated experiment explanation, when input rank has in limited time, in Open Shortest Path First OSPF (Open Shortest Path First) Routing Protocol, represents the election of router and the competition of inundation process will cause shaking.Basu etc. have studied the stability of ospf protocol in great detail by simulated experiment under a real network service provider's topological structure.Ye etc. have studied the dynamic optimization method of OSPF metric based on queuing model and online simulation experiment.Use Mathematical Modeling quantitative analyses such as Shaikh network congestion influence that route stability is caused, and the use test instrument has been verified analysis result under the simple topology model.In addition, researchers also design and have realized that the experiment bed provides the platform of routing algorithm evaluation and comparison, need to set employed routing algorithm and offered load before using the experiment bed, and the node and the link of configuration network one by one.Generally speaking, above-mentioned research or be based upon on the theory analysis perhaps is based upon in the simulated experiment based on model, lacks measurement and analysis to real system.Whether its result is suitable for real system, still needs practice further to verify.
In addition, some research is based on and measures actual Internet's.For example, through the passive measurements in 2 years and initiatively wrong the injection, Labovitz etc. find to need dozens of minutes could reach the route consistency once more after an Internet inter-domain routing mistake.Yet this class research method not only needs to drop into huge manpower and materials, and may produce certain destructiveness to existing network, therefore should not extensively carry out on a large scale.
In order to verify the characteristic of real system, an efficient ways is to set up test macro, and interconnected with actual system under test (SUT), tests.For example, a kind of network simulator uses fast parallel discrete event simulation kernel, and the means of a kind of IP layer network emulation are provided.Similarly, another simulator is when transmission from the source to the destination of Simulation with I P grouping, and it is mutual that fixing delay and real system can be set.Noble etc. have studied the replay method of end-to-end characteristics in the actual wireless network, and have guaranteed the data transparency that this technology is received and dispatched system under test (SUT) based on following the tracks of (Trace Modulation) technology of adjusting.Network Transmission control protocol under the support of the main network-oriented simulator of the interconnected test envelope of virtual network.The forwarding of IP grouping in the network is paid attention in these researchs, and lacks the consideration to the route grouping, does not more relate to the interaction characteristic of Routing Protocol.
More than in numerous researchs, do not see also with Routing Protocol and network topology model that the two combines and be used for the precedent of Routing Protocol test.Often from the angle of simulation, end-to-end characteristics etc. is then only paid attention in the research of network topology model to Research of Routing Protocols, and the routing characteristic shortage of network core device is considered.Though though comprised the Routing Protocol test function in some commercial tester product, but because shortage is to the support of Internet topological structure model, also lack cooperation between each port of test macro, they also can't provide perfect Internet route test function.
Summary of the invention
The object of the present invention is to provide a kind of Routing Protocol method of testing and system that is used for the Routing Protocol test based on break-through-terminal network model.
Method proposed by the invention is characterised in that: it is a kind of with the router Routing Protocol method of testing based on break-through-terminal network topology model of distributed real time operating system as development platform.It is at the test router of a reality, each node of break-through-terminal network topology model is represented a router, the physical link between the router is represented on every limit, and then according to the port number and the actual instructions for use of above-mentioned test router, in the above topology structure, look for a suitable node to represent above-mentioned test router, thereby make other all nodes and the mutual routing iinformation of above-mentioned test router, so that above-mentioned test router carries out the Routing Protocol test in such large-scale network environment.It contains following steps successively:
(1) according to the test router of reality, uses break-through-terminal network topology model, network size that configuration will be simulated and the interconnecting relation between each layer;
(2) simulation produces corresponding large-scale network topological model;
(3), locate the residing level of above-mentioned test router according to the port number and the node type of above-mentioned test router;
(4) judge whether there is the above-mentioned test router that satisfies condition in the above-mentioned network topology model,, then return step (2) if do not have;
(5) otherwise, above-mentioned network topology model is mapped as the Internet architecture that constitutes towards the inner agreement of using that Open Shortest Path First (OSPF) of each autonomous system AS by a plurality of autonomous system AS;
(6) according to the ospf protocol requirement, the 5th class link state advertisement LSA produces subsystem the outer link-state information of this autonomous system is changed into the 5th class link state advertisement, and sends to and the pairing protocol test subsystem of the direct-connected node of test router;
(7) select the port of a node that is connected with the break-through domain node of above-mentioned test router position for working as front port;
(8) in the AS at above-mentioned test router place, the 4th class LSA produces subsystem and produces the 4th class link state advertisement LSA for each AS border router, and these LSA are sent to when the pairing protocol test subsystem of front port;
(9) for determine inner other routers of corresponding AS when front port, the 1st～3 class link state advertisement LSA produces subsystem and forms the 1st～3 class link state advertisement according to protocol requirement in view of the above, and sends to the corresponding protocol test subsystems;
(10) each link state advertisement subsystem sends LSA through protocol test subsystem separately to above-mentioned test router and describes grouping;
(11) after above-mentioned test router receives corresponding description grouping, send LSA request grouping, and after the protocol test subsystem receives the request grouping, send corresponding LSA update packet, begin simultaneously each Link State renewal process timing;
(12) the protocol test subsystem is after receiving corresponding LSA affirmation grouping, and timing finishes;
(13) set by step all of the port of above-mentioned test router is handled in (7)～(12);
(14) statistical average time of delay and output;
(15) finish.
The mapping relations of the wherein described break-through of step (5)-terminal territory topological model TS and the Internet architecture are as follows:
The TS topological model---towards the Internet of BGP, OSPF
Whole topological model---the Internet
A break-through territory and all terminal territories that connected---autonomous system thereof
The link that connects different break-through territory---BGP interactive link
Break-through territory---OSPF backbone area
Terminal territory---the non-backbone area of OSPF
The node that connects different break-through territory---AS border router
Node in the break-through territory---ospf domain border router
Node---router in the ospf area in the terminal territory
The link that connects different terminal territories---ospf virtual link.
System based on the Routing Protocol method of testing of break-through-terminal network model is characterised in that: it be a kind of interconnection path by test macro IRTS, it contains: topology generates subsystem; Control above topology generation subsystem and the test router that links to each other with its data output end are chosen subsystem; The link state advertisement of choosing totally 5 classifications that the data output end of subsystem links to each other with above-mentioned test router produces subsystem LSA1～LSA5; Produce with above-mentioned LSA that the data output end of subsystem is corresponding respectively to be connected and to carry out the mutual N of a Routing Protocol protocol test subsystem with test router, wherein N is the port number of test router; Controlling respectively that above topology generates subsystem, test router is chosen the operation of subsystem and N protocol test subsystem and managed the OAM subsystem.
Experimental results show that it has reached intended purposes: model Network Based is realized the test of Routing Protocol.
Description of drawings
Fig. 1. break-through-terminal network topology model
Among Fig. 1: 1 is the break-through territory; 2 is terminal territory; 3 for connecting the terminal territory in a plurality of break-through territory.
Fig. 2. internet topological structure figure
Fig. 3. the refinement figure of node a: IF is an interface among Fig. 2.
Fig. 4. interconnection path is by overview flow chart.
Fig. 5. the used interconnection path of example is described by overview flow chart.
Fig. 6. interconnection path by test macro IRTS general structure and with the connection layout of test router RUT.
Fig. 7. the orderly federal data structure diagram of higher-dimension.
Fig. 8. the network topological diagram of being simulated that reality is given an example.
Fig. 9. the relation of answering delay and network size.
Figure 10. the higher-dimension curvilinear regression under the logarithmic coordinates.
Figure 11 .RUT chooses algorithm flow chart.
Embodiment
Because real network equipment (router) before putting into operation, often need carry out actual test according to the method for its use.Yet, test if directly put it in the practical large-scale network environment, in case this router is nonconforming so, may produce destructive influences to real network.In order to address this problem, we are based on the thought that simulation of Internet network topological diagram and Routing Protocol is realized combine, design has realized Internet route test macro IRTS (Intemet Routing TestingSystem), and its flow chart as shown in Figure 4.
Test router (Router Under Test is abbreviated as RUT) at a reality, we at first simulate a large-scale network topological structure that is similar to real network, wherein each node is represented a router, and the link between the router is represented on every limit.Then, we see how this RUT will really be applied in the actual environment, comprise the port number of RUT and the network-level at port place.And then according to the application request of RUT, dispose our system, thereby look for a suitable node to represent this RUT in the network of being simulated, the route test macro is then simulated other remaining all nodes (each node is represented a router) and is come and the mutual routing iinformation of RUT.Like this, at RUT, RUT itself is in the large-scale network environment, and and does not know that this is the environment of a simulation.Therefore, if RUT can illustrate that so RUT also can be according to the normally operation in real network of this application mode at the large-scale network environment of this simulation in normal, stable operation.
Below, we at first illustrate that by a simple example this system is how according to flow chart work.Illustrate as shown in Figure 8.At first dispose the network topological diagram that to simulate: the number Tranist=1 in break-through territory; Each break-through territory comprises the mean number Tnode=1 of break-through domain node; The mean number Stub=2 in each break-through terminal territory that domain node connects; The mean number Snode=1 of terminal domain node that each terminal territory comprises.Like this, the node that topological diagram comprised adds up to: (Transit * Tnode) * (Stub * Snode+1)=3, promptly as the network topological diagram among Fig. 2.Our type that disposes RUT is then: have two ports that belong to zones of different respectively, so we can only to select node a be RUT, and then we distinguish the route behavior of analog node b and node c, send routing iinformation to node a, thereby make node a be in the network topology structure that we simulate, realize the test of network route.
As the learning prototype system, IRTS has only realized OSPF (Open Shortest Path First) protocol test at present, system configuration as shown in Figure 6, comprise operation and management (Operation And Management, abbreviation OAM) subsystem, topology generate subsystem, RUT chooser system, link state advertisement (Link State Advertisement is called for short LSA) generation subsystem and protocol test subsystem.
OAM subsystem controls, coordination and dispose other subsystems according to customer requirements comprise the parameter of random network topological diagram, the parameter of RUT, the configuration of OSPF etc.It is on the basis of suitable network topology model that topology generates, and simulates the stratification random network topological diagram with practical significance, thereby represents the topological structure of current Internet to a certain extent.For improving the extensibility (as other topological models of later employing) of system, the result that topology generates stores with the GB form.RUT chooser system reads the topological diagram with the storage of GB form, and according to the OAM configuration, chooses suitable node as RUT in topological diagram, disposes the IP address of all each ports of node simultaneously.If do not satisfy the node of RUT configuration condition in current topological diagram, then the notice topology generates subsystem and produces topological diagram again.LSA produces subsystem then according to the particular location of RUT in topological diagram, is each specific LSA of node generation that directly links to each other with RUT, and sends to the corresponding protocol test subsystems.Move a plurality of protocol test subsystems in IRTS simultaneously, each protocol test subsystem is represented a node, is realizing on the mutual basis of Routing Protocol, sends the LSA generation LSA that subsystem produced to RUT.Wherein, each protocol test subsystem is the route behavior of a router of emulation independently, finishes corresponding route interactive function, thereby is the router of a telotism at RUT.Each protocol test subsystem carries out on the mutual basis of normal route, has upper-layer subsystem (LSA produces subsystem) control to send the LSA of simulation, thereby makes network of each protocol test subsystem emulation.
Then, we will be described in detail following two problems:
1. network topology mapping problems
In order to improve the extensibility of route, Internet mainly adopts the routing architecture of stratification at present: at first Internet is divided into a plurality of autonomous system AS (Autonomous System), the main Border Gateway Protocol (Border GatewayProtocol is called for short BGP) that adopts between the AS; Inner ospf protocol or the routing information protocol (Routing Information Protocol is called for short RIP) used of AS.The RIP protocol application is in mininet, and this paper mainly inquires into the topological structure of BGP and OSPF Routing Protocol correspondence.AS for adopting ospf protocol is divided into several zones (Area) usually again, is connected each zone of lower floor by the node (trunk node) in trunk (Backbone) zone.Like this, Internet is become three layers by man-made division: i.e. AS, zone, node.As 5 zone: A0 being arranged to A4 among the autonomous system AS1 that Fig. 2 comprised, wherein A0 is a trunk.
It may be noted that BGP and OSPF are also inequality for the dividing mode of network: for BGP, each node belongs to an AS; And for OSPF, each port of router belongs to a zone.The port of a so-called router is exactly socket or the outlet that this router is used for connecting other routers.For example, node c belongs to AS1 among Fig. 2; And among four port IF1, the IF2 of node a connected node b, c, d, e, IF3, the IF4, IF1 and IF2 belong to regional A0, and IF3 belongs to A2, IF4 belongs to A1, therefore node a does not belong to some specific zones, such node is called Area Border Router, and promptly a plurality of ports of this node belong to different zones.
Because different topological models causes the topological diagram of simulating with generating different, and the performance of Routing Protocol and algorithm depends on applied topological environmental probably.Therefore in order to test the routing characteristic under real network environment, need choose the topological model identical with the Internet topological structure.Network topology model commonly used at present comprises following several: the 1) topological structure of simple rule, as star-like connection, ring-like connection, the connection of tree type, network etc.; 2) well-known topological structure is as ARPAnet, NFSnet, MCI backbone domain etc.; 3) topological structure that generates at random.Along with the continuous Free Development of Internet, its structure and any specific structure have all had very big difference; Simultaneously, for the stochastic and dynamic of Simulation with I nternet, we select the 3rd type for use, i.e. the random topology model.GT-ITM is a typical random topology figure Core Generator, and it can produce the random topology figure based on plane stochastic model, N hierarchical model and break-through-terminal model.Wherein, break-through-end (Transit-Stub) TS model can be represented current Internet structure as shown in Figure 1, so we select this model for use.
Each dark ellipse is represented a break-through territory (Transit Domain) among the figure, and each light circle is represented a terminal territory (Stub Domain), thereby the Internet structure of stratification is provided.This model can be provided with following parameter: the number T in break-through territory; Each break-through territory comprises the mean number N1 of break-through domain node; The mean number K in each break-through terminal territory that domain node connects; The mean number N2 of terminal domain node that each terminal territory comprises.Like this, the node that topological diagram comprised adds up to: (T * N1) * (K * N2+1).When the number of degrees of node were not too big, the number scale of subnet was suitable in node number and the network.
This model provides a topological diagram with three-decker, each layer itself can adopt the control mode of plane Random Graph to control, and support the various configurations in break-through territory, terminal territory and the control of correlation are had stronger model and parameter ability is set.
According to different levels, the Internet topological structure can be divided into multiple.For example, be planar structure from data link layer Internet, be double-layer structure from BGP and RIP Internet, and have three-decker from BGP and OSPF Internet.Therefore, above-mentioned TS model need be corresponded in the Internet topological structure of BGP and OSPF, as shown in table 1.By such corresponding relation, and remove the terminal territory that has connected a plurality of break-through territory simultaneously, we have finished the TS topological model and have opened up to Internet
The corresponding relation of table 1 TS model and Internet
| The TS topological model | Internet towards BGP, OSPF |
| Whole topological model | Internet |
| A break-through territory and all terminal territories that connected thereof | An autonomous system |
| The link that connects different break-through territory | The BGP interactive link |
| The break-through territory | The OSPF backbone area |
| Terminal territory | The non-backbone area of OSPF |
| The node that connects different break-through territory | The AS border router |
| Node in the break-through territory | The ospf domain border router |
| Node in the terminal territory | Router in the ospf area |
| The link that connects different terminal territories | Ospf virtual link |
Pounce on the conversion of structure.
2. tested node is chosen problem
In order to test the route interaction characteristic of RUT in Internet, must be according to the actual occupation mode configuration IRTS of RUT, comprise status (as affiliated area) in Internet of RUT port number, each port, IP address etc.For example, require RUT to have four ports, and have in the backbone area in two ports, other two zones a port is respectively arranged, then can select the node a among Fig. 2 is RUT.At this moment, IRTS moves 4 protocol test subsystems altogether, the route behavior of simulation node b, c, d, e respectively, thus the network topological information of realizing whole Internet on the route aspect is mutual.
Carry out RUT when choosing, adopt higher-dimension sequential chained list data structure as shown in Figure 7.At certain the node N in the topological diagram, check the port that they are all, and according to the ordering of territorial classification that this node connected: all of the port that will belong to same zone couples together with chained list, again with how many orderings (backbone area rank the first) of zone, thereby obtain the higher-dimension sequential chained list L of node N according to having port
NRUT chooses algorithm as shown in figure 11, and wherein CAL (N) is the higher-dimension sequential chained list L of computing node N
NWhen parameter was RUT, then result of calculation was the pairing higher-dimension sequential chained list of RUT L
RUTWith calculating L
NMethod similar, at first the actual using method according to RUT disposes RUT, what zones promptly dispose RUT has, the port number that each zone had, thus calculate the pairing higher-dimension sequential chained list of RUT L
RUTThen with topological diagram in the pairing L of each node
NRelatively, up to finding a node L
RUTWith L
NCoupling, i.e. L
RUTWith L
NThe number of regions that is comprised is identical and port number that each zone is interior is identical.The computation complexity of function C AL (N) is O (If
2), it is O (K * If that RUT chooses the total complexity of algorithm
2), wherein K is the number of node in the topological diagram, If is the maximum of the port number that arbitrary node had.Because topological diagram has a large amount of similar nodes usually, often need not travel through all nodes and just may find the node that is fit to the RUT configuration, therefore above-mentioned complexity is the time complexity of worst condition (RUT chooses mistake).
Choose suitable node as RUT after, also need port arrangement IP address for whole each node of network.Because OSPF do not use IP address aggregation strategy, therefore for for simplicity, the user only need dispose the IP address of RUT and IRTS port, and the network model home address then generates automatically.Algorithm at first is provided with RUT and adjacent Port IP address thereof, checks each node then one by one, be provided with this node port and the IP address of direct-connected the other side's port.For saving address space to adapt to the demand of large scale network model, every link uses the subnet of a mask as 255.255.255.252, and two ports of link use two available host addresses in this subnet respectively.
Based on above-mentioned technology, Tsing-Hua University has successfully developed distributed Internet route test macro IRTS, and has realized strength test.This system uses the distributed multiprocessor based on the Compact pci bus, selects the distributed real time operating system VxWorks as development platform.Its master control borad uses Motorola MPC750 processor, and operation OAM subsystem, topology generate subsystem, RUT chooser system and LSA and produce subsystem.Ply-yarn drill uses Motorola 860 processors, mainly moves the protocol test subsystem, and ply-yarn drill uses FPGA to realize that multiple ether connects net and WAN port, comprises gigabit ethernet port, 100 m ethernet port and 2M synchronous port.
Use the IRTS of designed realization to be the experiment bed, the route reciprocal process when in Internet, starting by test CISCO2600 router, we have carried out strength test to the CISCO2600 router.Test process hypothesis when RUT starts, other routers of network alternately in order, each router has corresponding routing table and link-state information storehouse.Test process has realized that the extensive high speed OSPF route between whole network and the RUT is mutual.By its interaction characteristic of Measurement and analysis, we have obtained the computation complexity and the capacity of the OSPF realization of RUT and have supported the upper limit.Description of test IRTS has well realized system design goal.
Fig. 9 has represented the answering delay of link state advertisement (LSA) and the relation between the network size in the test process.Y-axis represents that the IRTS system sends a LSA to receiving the mathematic expectaion E (D) that postpones D between the respective acknowledgement, and X-axis N represents employed network size, i.e. the subnet number.
At first to this figure qualitative analysis.In scale N＜4000 o'clock, Y=E (D)=F (N) is the decreasing function of independent variable N.This explanation after the OSPF of RUT is implemented in and receives link-state information, is carried out delayed response (DelayedAcknowledge) according to consensus standard.In this answering, when RUT receives a LSA, do not send the Ack packet acknowledgment at once, but after waiting for certain time interval or receiving the LSA of some (replying thresholding), produce a response message again and confirm these LSA, thereby for saving bandwidth, increasing network throughput.But because the limited amount of LSA, reciprocal process last total some still its quantity of LSA of dont answer do not reach RUT and reply thresholding, so RUT can be in wait state, more LSA is received in expectation, up to overtime.The delay of this part LSA is bigger, and we claim that this is the LSA that is in wait state owing to delayed response causes postponing very big LSA.And LSA before this is very fast owing to inbound pacing, and the stand-by period was compared and can ignore with the processing time of RUT, therefore can think that these LSA do not have latency delays.Along with the number increase of LSA, the LSA shared ratio in all LSA that is in wait state constantly reduces, so E (D) reduces along with the increase of N.
When N constantly increased, because RUT constantly carries out LSD operation, calculating shortest path tree, and the calculating scale also constantly enlarged, the RUT processor load increases, processing time increases, and shows as the LSA that can not in time acknowledge receipt of, so E (D) increases with the increase of N.
Adopt the data of statistical model quantitative analysis Fig. 9 below.Because the excursion of N is bigger, at first N is taken the logarithm, and makes abscissa X=ln (N), ordinate Y=E (D) passes through the least square fitting curve, as shown in figure 10 on logarithmic coordinates figure.Secondary, three times and biquadratic curve recurrence have been carried out among the figure respectively.As can be seen, biquadratic curve returns and approaches test data, illustrates that the extensibility of RUT is higher, can adapt to large-scale network environment preferably, its performance E (D) ∝ O ((lnN)
4).This biquadratic curve equation is:
E(D)＝0.0160(lnx)
4-0.4082(lnx)
3+3.8641(lnx)
2-16.4158(lnx)+28.8157
By above-mentioned empirical equation extrapolation, the mathematic expectaion of the LSA answering delay time of RUT in the time of can estimating N for other numerical value.For example work as N=43,000 o'clock, E (D)=5.10s.Because consensus standard regulation,, therefore at this moment, the processing speed of RUT do not cause a large amount of LSA to retransfer owing to catching up with if do not receive in 5 seconds that confirmation just resends update packet.If this thing happens, not only can waste massive band width, and can cause serious burden RUT, cause RUT efficient sharply to descend even lost efficacy, can think that therefore this is the upper limit of the route table items number that can bear of RUT.
This shows that the present invention has reached the intended purposes that model Network Based is realized the Routing Protocol test.
Claims (3)
1. based on the Routing Protocol method of testing of break-through-terminal network model, used the break-through-terminal topological model TS that generates at random, it is characterized in that: it is a kind of with the router Routing Protocol method of testing based on break-through-terminal network topology model of distributed real time operating system as development platform, it is at the test router of a reality, each node of break-through-terminal network topology model is represented a router, the physical link between the router is represented on every limit, and then according to the port number and the actual instructions for use of above-mentioned test router, in the above topology structure, look for a suitable node to represent above-mentioned test router, thereby make other all nodes and the mutual routing iinformation of above-mentioned test router, so that above-mentioned test router carries out the Routing Protocol test in such large-scale network environment; It contains following steps successively:
(1) according to the test router of reality, uses break-through-terminal network topology model, dispose the interconnecting relation between this network size and each layer;
(2) produce corresponding large-scale network topological model;
(3), locate the residing level of above-mentioned test router according to the port number and the node type of above-mentioned test router;
(4) judge whether there is the above-mentioned test router that satisfies condition in the above-mentioned network topology model,, then return step (2) if do not have;
(5) otherwise, above-mentioned network topology model is mapped as the Internet architecture that constitutes towards the inner ospf protocol of using that Open Shortest Path First of each autonomous system AS by a plurality of autonomous system AS;
(6) according to the ospf protocol requirement, the 5th class link state advertisement LSA produces subsystem the outer link-state information of this autonomous system is changed into the 5th class link state advertisement, and sends to and the pairing protocol test subsystem of the direct-connected node of test router;
(7) select the port of a node that is connected with the break-through domain node of above-mentioned test router position for working as front port;
(8) in the AS at above-mentioned test router place, the 4th class LSA produces subsystem and produces the 4th class link state advertisement LSA for each AS border router, and these LSA are sent to when the pairing protocol test subsystem of front port;
(9) for determine inner other routers of corresponding AS when front port, the 1st～3 class link state advertisement LSA produces subsystem and forms the 1st～3 class link state advertisement according to protocol requirement in view of the above, and sends to the corresponding protocol test subsystems;
(10) each link state advertisement subsystem sends LSA through protocol test subsystem separately to above-mentioned test router and describes grouping;
(11) after above-mentioned test router receives corresponding description grouping, send LSA request grouping, and after the protocol test subsystem receives the request grouping, send corresponding LSA update packet, begin simultaneously each Link State renewal process timing;
(12) test router is defined in to receive according to ospf protocol and will sends LSA after the LSA update packet and confirm grouping, and the protocol test subsystem is receiving after corresponding LSA confirms grouping, and timing finishes;
(13) set by step all of the port of above-mentioned test router is handled in (7)～(12);
(14) statistical average time of delay and output;
(15) finish.
2. according to the described Routing Protocol method of testing based on break-through-terminal network model of claim 1, it is characterized in that: the mapping relations of the wherein described break-through of step (5)-terminal territory topological model TS and the Internet architecture are as follows:
The TS topological model---towards the Internet of BGP, OSPF;
Whole topological model---the Internet;
A break-through territory and all terminal territories that connected---autonomous system thereof;
The link that connects different break-through territory---BGP interactive link;
Break-through territory---OSPF backbone area;
Terminal territory---the non-backbone area of OSPF;
The node that connects different break-through territory---AS border router;
Node in the break-through territory---ospf domain border router;
Node---router in the ospf area in the terminal territory;
The link that connects different terminal territories---ospf virtual link.
3. based on the system of the Routing Protocol method of testing of break-through-terminal network model, it is characterized in that: it is that a kind of interconnection path is by test macro IRTS, it contains: topology generates subsystem, test router is chosen subsystem, link state advertisement produces subsystem LSA1～LSA5, the protocol test subsystem, operation and management OAM subsystem, wherein test router is chosen subsystem controls above topology generation subsystem and is linked to each other with its data output end, link state advertisement produces subsystem and above-mentioned test router and chooses the link state advertisement that the data output end of subsystem links to each other and produces 5 classifications, the data output end that protocol test subsystem and above-mentioned LSA produce subsystem is connected and to carry out Routing Protocol mutual with test router, operation and management OAM subsystem controls above topology generation subsystem, test router is chosen subsystem, link state advertisement produces subsystem and protocol test subsystem.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CNB02146040XA CN1153417C (en) | 2002-10-25 | 2002-10-25 | Simulation method and system for priority protocal of Internet large-scale route to open shortest path |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CNB02146040XA CN1153417C (en) | 2002-10-25 | 2002-10-25 | Simulation method and system for priority protocal of Internet large-scale route to open shortest path |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN1404268A CN1404268A (en) | 2003-03-19 |
| CN1153417C true CN1153417C (en) | 2004-06-09 |
Family
ID=4750993
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CNB02146040XA Expired - Fee Related CN1153417C (en) | 2002-10-25 | 2002-10-25 | Simulation method and system for priority protocal of Internet large-scale route to open shortest path |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN1153417C (en) |
Families Citing this family (25)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN100407606C (en) * | 2003-03-20 | 2008-07-30 | 华为技术有限公司 | Method for detecting mobile gateway node repeating power |
| JP4231766B2 (en) * | 2003-10-24 | 2009-03-04 | 株式会社日立コミュニケーションテクノロジー | A communication apparatus and a communication method for performing path control between ASs. |
| EP1705841A4 (en) * | 2003-12-24 | 2010-07-21 | Ntt Docomo Inc | Network topology generation method and node |
| CA2467945A1 (en) * | 2004-05-20 | 2005-11-20 | Fernando Cuervo | Open service discovery and routing mechanism for configuring cross-domain telecommunication services |
| GB0416272D0 (en) * | 2004-07-20 | 2004-08-25 | British Telecomm | Method of operating a network |
| CN100366003C (en) * | 2005-04-28 | 2008-01-30 | 华为技术有限公司 | Device and method for emulated route analysis test |
| CN101286921B (en) * | 2007-05-16 | 2012-07-25 | 清华大学 | User-oriented cross-domain network route terminal-to- terminal selection method on Internet |
| CN101510870B (en) * | 2008-04-23 | 2012-03-21 | 北京德瑞海普科技有限公司 | Method for simulating, verifying and organizing code grade network protocol based on script and module drive |
| US9253038B2 (en) | 2008-08-08 | 2016-02-02 | Hewlett-Packard Development Company, L.P. | End-to-end network access analysis |
| CN101567818B (en) * | 2008-12-25 | 2011-04-20 | 中国人民解放军总参谋部第五十四研究所 | Large-scale network routing simulation method based on hardware |
| CN101515899B (en) * | 2009-04-01 | 2012-05-23 | 中国人民解放军信息工程大学 | Route generation method and device |
| CN101552694B (en) * | 2009-05-12 | 2011-07-20 | 成都市华为赛门铁克科技有限公司 | Network topology loading method, device and network management system |
| WO2011079463A1 (en) * | 2009-12-31 | 2011-07-07 | Nokia Corporation | Method and apparatuses for testing on-line services |
| CN101925102B (en) * | 2010-06-08 | 2012-10-17 | 中国人民解放军理工大学 | Wireless network topology simulation method adopting Ethernet promiscuous mode |
| CN101877675B (en) * | 2010-06-09 | 2014-04-16 | 清华大学 | Cross-domain BGP policy adjustment and control effect estimation method and device VTGCS |
| CN101867503B (en) * | 2010-06-09 | 2012-12-26 | 清华大学 | Cross-domain BGP routing policy deployment method |
| CN102420797B (en) * | 2010-09-27 | 2014-10-22 | 北京系统工程研究所 | Topology mapping method and system |
| CN102932116B (en) * | 2012-10-26 | 2015-06-17 | 迈普通信技术股份有限公司 | Link state advertisement information confirmation method and equipment |
| CN103269294B (en) * | 2013-04-26 | 2016-08-17 | 广东电网公司电力科学研究院 | The method of testing of message based on ESB bus route and system |
| CN104065573A (en) * | 2014-06-30 | 2014-09-24 | 重庆邮电大学 | Routing method based on least-squares fitting in multi-domain optical network |
| CN108259387B (en) * | 2017-12-29 | 2020-12-22 | 曙光信息产业(北京)有限公司 | Switching system constructed by switch and routing method thereof |
| CN113315647B (en) * | 2020-09-14 | 2024-10-15 | 阿里巴巴集团控股有限公司 | Network simulation method and device |
| CN113193998B (en) * | 2021-04-27 | 2022-11-15 | 清华大学 | Network emulation method, programmable switch, and computer-readable storage medium |
| CN113794732B (en) * | 2021-09-22 | 2023-08-11 | 上海观安信息技术股份有限公司 | Method, device, equipment and storage medium for deploying simulation network environment |
| CN116192657B (en) * | 2022-12-29 | 2024-10-18 | 中国联合网络通信集团有限公司 | Network ISIS route diffusion simulation method and device |
-
2002
- 2002-10-25 CN CNB02146040XA patent/CN1153417C/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| CN1404268A (en) | 2003-03-19 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN1153417C (en) | Simulation method and system for priority protocal of Internet large-scale route to open shortest path | |
| Baumgart et al. | OverSim: A flexible overlay network simulation framework | |
| Zheng et al. | Empower: A network emulator for wireline and wireless networks | |
| Millberg et al. | The Nostrum backbone-a communication protocol stack for networks on chip | |
| CN103179052B (en) | A kind of based on the central virtual resource allocation method and system of the degree of approach | |
| CN103685583B (en) | A kind of method and system of domain name mapping | |
| CN103023967B (en) | Cloud computing simulation system and method based on simics system simulator | |
| Kumar et al. | Ns3 simulator for a study of data center networks | |
| Chen et al. | DAC: Generic and automatic address configuration for data center networks | |
| JP2012532481A (en) | Method and device for evaluating interconnection efficiency of parallel computer networks based on static routing scheme | |
| Hsu et al. | Virtual network mapping algorithm in the cloud infrastructure | |
| Yuan et al. | Lfti: A new performance metric for assessing interconnect designs for extreme-scale hpc systems | |
| Momeni et al. | Improving a computer networks course using the Partov simulation engine | |
| Ahmed et al. | Scalable interconnection network models for rapid performance prediction of HPC applications | |
| Zhu et al. | IETF IoT based wireless communication for latency-sensitive use cases in building automation | |
| Reddy et al. | Performance assessment of different Network-on-Chip topologies | |
| Sadiku et al. | Effect of Traditional and Software-Defined Networking on Performance of Computer Network | |
| Schneider et al. | An Oblivious Routing Congestion Simulator | |
| Zheng et al. | Empower: A cluster architecture supporting network emulation | |
| CN110191382A (en) | A kind of virtual link priority mapping method based on paths ordering | |
| CN117081983B (en) | Data transmission method and device | |
| Wu et al. | A comparative analysis of server selection in content replication networks | |
| CN1305279C (en) | Non-state end-to-end constraint entrance permit control method for kernel network | |
| Gil-Costa et al. | Service deployment algorithms for vertical search engines | |
| Johari et al. | Master-based routing algorithm and communication-based cluster topology for 2D NoC |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| C19 | Lapse of patent right due to non-payment of the annual fee | ||
| CF01 | Termination of patent right due to non-payment of annual fee |