【文章內(nèi)容簡(jiǎn)介】 each other. (See Figure 1.) Stub domains generally correspond to campus works or other collections of interconnected LANs, while transit domains are almost always wideor metropolitanarea works (WANs or MANs). Figure 1. Example of Inter domain structure A transit domain consists of a set of backbone nodes. In a transit domain each backbone node may also connect to a number of stub domains, via gateway nodes in the stubs. Some backbone nodes also connect to other transit domains. Stub domains can be further classified as singleor multihomed. Multihomed stub domains have connections to more than one transit domain。 singlehomed stubs connect to only one transit domain. Some stubs domains may have links to other stubs. Transit domains may themselves be anized in hierarchies, . MANs connect mainly to stubs domains and WANs. Existing Topology Models One of the most monly used models for generating random works algorithmically is due to Waxman [3]. The nodes in the work are placed at random points in a two dimensional grid. Links (represented by edges between nodes) are added to the work by considering all possible pairs of nodes and then deciding whether a link should exist according to a probability function involving how far apart the two nodes are and how many links are expected to be in the whole work. The original intention of this approach was to generate works for paring Minimum Steiner Tree algorithms. It has several serious drawbacks when used for generating typical 湖北大學(xué)本科畢業(yè)論文（設(shè)計(jì)） 外文翻譯 10 inters. First, the works don39。t resemble the handdrawn topological maps of real works. There is no sense of a backbone or hierarchy, and the existence of links clear across the work is unrealistic. Second, it does not guarantee a connected work. Each generated work must be checked for connectivity, then discarded or modified if the check fails. Either option involves extra work. Third, as the number of nodes in the work grows, the number of links grows in a similar fashion. This is unlike real works, where new links are added for redundancy, not just because more nodes joined the work. Various modifications to Waxman39。s method have been proposed by the authors and others. Some of these attempts to restrict the longest links in the work, while others reduce the number of edges from any particular node. Still other modifications introduce a simple hierarchy to the work. None of them produce convincingly realistic works. 2 A Better Method Over the past few years a better method has been devised independently by the authors for generating graphs that reflect the hierarchical domain structure and locality that is present in the Inter [1, 4]. Three levels of hierarchy are modeled, corresponding to transit domains, stub domains, and LANs attached to stub nodes. The method constructs the graph piecewise, where the pieces correspond to domains at the different levels in the hierarchy. The connectivity within a domain (intra work connectivity) is dealt with separately from that between domains (interwork connectivity). Parameters Two sets of parameters control the coarse properties of the works generated. These parameters are chosen to provide reasonably simple control over the important structural characteristics of the graph. The parameters chosen also have obvious effects on the works that are produced. The first set of parameters governs the relative sizes of the three levels in the hierarchy: T, the total number of transit domains, and NT, the average number of nodes per transit domain. Note that= 1 and NT=1. S, the average number of stub domains per transit domain, and NS, the average number of nodes per stub domain. Note that S= 1 and NS=1. L, the average number of LANs per stub node, and NL, the average number of hosts per LAN. LANs are modeled as star topologies with a router node at the center of the star and the host nodes each connected to the center router. As pared to using a plete graph connecting all hosts in the LAN, this significantly reduces the number of edges in the graph and reflects the lack of physical redundancy in most LANs. Note that L= 0 and NL=1. The total number of routing nodes, NR, and the total number of hosts, NH are given by: NR =TNT(1 + SNs) NH =TNTSNSLNL Note that the parameter values are taken as the basis for distributions used to obtain the actual value for each run of the algorithm. Extra information can be associated with each parameter to describe the distribution of the parameter. For instance, an upper and lower bound on the number of nodes in a stub domain and the function for distributing the value between the bounds could be described. 湖北大學(xué)本科畢業(yè)論文（設(shè)計(jì)） 外文翻譯 11 The second set of parameters governs the connectivity within a domain (intrawork connectivity) and the connectivity between domains at the same or higher and lower levels (interwork connectivity). ET, the average number of edges from a transit node to other transit nodes in the same must be large enough so that the graph corresponding to each transit domain can be connected. (ET= 2.) ES, the average number of edges from a stub node to other stub nodes in the same domain. ES must be large enough so that the graph corresponding to each stub domain can be connected. (ES=2.) ETT, the average number of edges from a transit domain to another transit domain. ETT must be large enough so that the transit domains can be connected to one another. . (ETT =2.) EST , the average number of edges from a stub domain to a transit domain. Every stub domain must be connected to at least one transit domain, thus EST =1。 multihomed stub domains will have more than one edge to a transit domain. ELS, the average number of edges from a LAN to a stub node. Every LAN must be connected to at least one stub node, thus ELS= 1. LANs