Loading [MathJax]/jax/output/SVG/jax.js

The many facets of internet topology and traffic

  • Received: 01 September 2006
  • Primary: 90B15; Secondary: 90B10.

  • The Internet's layered architecture and organizational structure give rise to a number of different topologies, with the lower layers defining more physical and the higher layers more virtual/logical types of connectivity structures. These structures are very different, and successful Internet topology modeling requires annotating the nodes and edges of the corresponding graphs with information that reflects their network-intrinsic meaning. These structures also give rise to different representations of the traffic that traverses the heterogeneous Internet, and a traffic matrix is a compact and succinct description of the traffic exchanges between the nodes in a given connectivity structure. In this paper, we summarize recent advances in Internet research related to (i) inferring and modeling the router-level topologies of individual service providers (i.e., the physical connectivity structure of an ISP, where nodes are routers/switches and links represent physical connections), (ii) estimating the intra-AS traffic matrix when the AS's router-level topology and routing configuration are known, (iii) inferring and modeling the Internet's AS-level topology, and (iv) estimating the inter-AS traffic matrix. We will also discuss recent work on Internet connectivity structures that arise at the higher layers in the TCP/IP protocol stack and are more virtual and dynamic; e.g., overlay networks like the WWW graph, where nodes are web pages and edges represent existing hyperlinks, or P2P networks like Gnutella, where nodes represent peers and two peers are connected if they have an active network connection.

    Citation: D. Alderson, H. Chang, M. Roughan, S. Uhlig, W. Willinger. The many facets of internet topology and traffic[J]. Networks and Heterogeneous Media, 2006, 1(4): 569-600. doi: 10.3934/nhm.2006.1.569

    Related Papers:

    [1] Xue Chang . The impact of corporate tax outcomes on forced CEO turnover. National Accounting Review, 2022, 4(3): 218-236. doi: 10.3934/NAR.2022013
    [2] Jinhui Zhu, Zhenghui Li . Can digital financial inclusion effectively stimulate technological Innovation of agricultural enterprises?—A case study on China. National Accounting Review, 2021, 3(4): 398-421. doi: 10.3934/NAR.2021021
    [3] Pavel Ivanov, Tatyana Altufeva . Stimulating the processes of attracting investments in industry of the constituent entities of the Russian Federation. National Accounting Review, 2024, 6(3): 352-366. doi: 10.3934/NAR.2024016
    [4] Fabrizio Antolini . Evaluating public expenditures on tourism: the utility of the Italian public accounting reforms. National Accounting Review, 2021, 3(2): 179-203. doi: 10.3934/NAR.2021009
    [5] Sweta C. Saxena, Giuseppe Tesoriere, Syed T. Ahmed, Wafa Aidi . Building new social contracts: a critical review of ideas and actions to fulfill African aspirations through education. National Accounting Review, 2025, 7(1): 85-105. doi: 10.3934/NAR.2025004
    [6] Shan Huang, Khor Teik Huat, Zifei Zhou . The studies on Chinese traditional culture and corporate environmental responsibility: literature review and its implications. National Accounting Review, 2022, 4(1): 1-15. doi: 10.3934/NAR.2022001
    [7] Jaroslav Sedláček, Veronika Popelková . Non-financial information and their reporting—evidence of small and medium-sized enterprises and large corporations on the Czech capital market. National Accounting Review, 2020, 2(2): 204-216. doi: 10.3934/NAR.2020012
    [8] Daniel Francois Meyer . Economic sectoral diversification: A case study of the Gauteng provincial region, South Africa. National Accounting Review, 2023, 5(4): 356-372. doi: 10.3934/NAR.2023021
    [9] Francesco Scalamonti . A quantitative and qualitative macroeconomic and sociopolitical outlook of the MEDA transitional economies: development-paths, governance climate, and sociocultural factors. National Accounting Review, 2024, 6(3): 407-448. doi: 10.3934/NAR.2024019
    [10] Serena Fatica, Wildmer Daniel Gregori . Income shifting by multinational enterprises as a source of mismeasurement in aggregate statistics. National Accounting Review, 2024, 6(4): 548-563. doi: 10.3934/NAR.2024025
  • The Internet's layered architecture and organizational structure give rise to a number of different topologies, with the lower layers defining more physical and the higher layers more virtual/logical types of connectivity structures. These structures are very different, and successful Internet topology modeling requires annotating the nodes and edges of the corresponding graphs with information that reflects their network-intrinsic meaning. These structures also give rise to different representations of the traffic that traverses the heterogeneous Internet, and a traffic matrix is a compact and succinct description of the traffic exchanges between the nodes in a given connectivity structure. In this paper, we summarize recent advances in Internet research related to (i) inferring and modeling the router-level topologies of individual service providers (i.e., the physical connectivity structure of an ISP, where nodes are routers/switches and links represent physical connections), (ii) estimating the intra-AS traffic matrix when the AS's router-level topology and routing configuration are known, (iii) inferring and modeling the Internet's AS-level topology, and (iv) estimating the inter-AS traffic matrix. We will also discuss recent work on Internet connectivity structures that arise at the higher layers in the TCP/IP protocol stack and are more virtual and dynamic; e.g., overlay networks like the WWW graph, where nodes are web pages and edges represent existing hyperlinks, or P2P networks like Gnutella, where nodes represent peers and two peers are connected if they have an active network connection.


    Cluster algebras were invented by Fomin and Zelevinsky in a series of papers [9,2,10,11]. A cluster algebra is a Z-subalgebra of an ambient field F=Q(u1,,un) generated by certain combinatorially defined generators (i.e., cluster variables), which are grouped into overlapping clusters. Many relations between cluster algebras and other branches of mathematics have been discovered, for example, Poisson geometry, discrete dynamical systems, higher Teichmüller spaces, representation theory of quivers and finite-dimensional algebras.

    We first recall the definition of cluster automorphisms, which were introduced by Assem, Schiffler and Shamchenko in [1].

    Definition 1.1 ([1]). Let A=A(x,B) be a cluster algebra, and f:AA be an automorphism of Z-algebras. f is called a cluster automorphism of A if there exists another seed (z,B) of A such that

    (1)f(x)=z;

    (2) f(μx(x))=μf(x)(z) for any xx.

    Cluster automorphisms and their related groups were studied by many authors, and one can refer to [6,7,8,14,13,4,5,16] for details.

    The following very insightful conjecture on cluster automorphisms is by Chang and Schiffler, which suggests that we can weaken the conditions in Definition 1.1. In particular, it suggests that the second condition in Definition 1.1 can be obtained from the first one and the assumption that f is a Z-algebra homomorphism.

    Conjecture 1. [5,Conjecture 1] Let A be a cluster algebra, and f:AA be a Z-algebra homomorphism. Then f is cluster automorphism if and only if there exist two clusters x and z such that f(x)=z.

    The following is our main result, which affirms the Conjecture 1.

    Theorem 3.6 Let A be a cluster algebra, and f:AA be a Z-algebra homomorphism. Then f is a cluster automorphism if and only if there exist two clusters x and z such that f(x)=z.

    In this section, we recall basic concepts and important properties of cluster algebras. In this paper, we focus on cluster algebras without coefficients (that is, with trivial coefficients). For a positive integer n, we will always denote by [1,n] the set {1,2,,n}.

    Recall that B is said to be skew-symmetrizable if there exists an positive diagonal integer matrix D such that BD is skew-symmetric.

    Fix an ambient field F=Q(u1,u2,,un). A labeled seed is a pair (x,B), where x is an n-tuple of free generators of F, and B is an n×n skew-symmetrizable integer matrix. For k[1,n], we can define another pair (x,B)=μk(x,B), where

    (1) x=(x1,,xn) is given by

    xk=ni=1x[bik]+i+ni=1x[bik]+ixk

    and xi=xi for ik;

    (2) B=μk(B)=(bij)n×n is given by

    bij={bij,if i=k or j=k;bij+sgn(bik)[bikbkj]+,otherwise.

    where [x]+=max{x,0}. The new pair (x,B)=μk(x,B) is called the mutation of (x,B) at k. We also denote B=μk(B).

    It can be seen that (x,B) is also a labeled seed and μk is an involution.

    Let (x,B) be a labeled seed. x is called a labeled cluster, elements in x are called cluster variables, and B is called an exchange matrix. The unlabeled seeds are obtained by identifying labeled seeds that differ from each other by simultaneous permutations of the components in x, and of the rows and columns of B. We will refer to unlabeled seeds and unlabeled clusters simply as seeds and clusters respectively, when there is no risk of confusion.

    Lemma 2.1 ([2]). Let B be an n×n skew-symmetrizable matrix. Then μk(B)=(Jk+Ek)B(Jk+Fk), where

    (1) Jk denotes the diagonal n×n matrix whose diagonal entries are all 1s, except for 1 in the k-th position;

    (2) Ek is the n×n matrix whose only nonzero entries are eik=[bik]+;

    (3) Fk is the n×n matrix whose only nonzero entries are fkj=[bkj]+.

    Definition 2.2 ([9,11]). (1) Two labeled seeds (x,B) and (x,B) are said to be mutation equivalent if (x,B) can be obtained from (x,B) by a sequence of mutations;

    (2) Let Tn be an n-regular tree and valencies emitting from each vertex are labelled by 1,2,,n. A cluster pattern is an n-regular tree Tn such that for each vertex tTn, there is a labeled seed Σt=(xt,Bt) and for each edge labelled by k, two labeled seeds in the endpoints are obtained from each other by seed mutation at k. We always write

    xt=(x1;t,x2;t,,xn;t),Bt=(btij).

    The cluster algebra A=A(xt0,Bt0) associated with the initial seed (xt0,Bt0) is a Z-subalgebra of F generated by cluster variables appeared in Tn(xt0,Bt0), where Tn(xt0,Bt0) is the cluster pattern with (xt0,Bt0) lying in the vertex t0Tn.

    Theorem 2.3 (Laurent phenomenon and positivity [11,15,12]). Let A=A(xt0,Bt0) be a cluster algebra. Then each cluster variable xi,t is contained in

    Z0[x±11;t0,x±12;t0,,x±1n;t0].

    In this section, we will give our main result, which affirms the Conjecture 1.

    Lemma 3.1. Let 0B be a skew-symmetrizable integer matrix. If B is obtained from B by a sequence of mutations and B=aB for some aZ, then a=±1 and B=±B.

    Proof.. Since B is obtained from B by a sequence of mutations, there exist integer matrices E and F such that B=EBF, by Lemma 2.1. If B=aB, then we get B=aE(B)F. Also, we can have

    B=aE(B)F=a2E2(B)F2==asEs(B)Fs,

    where s0. By B0, we know a0. Thus 1asB=Es(B)Fs holds for any s0.

    Assume by contradiction that a±1, then when s is large enough, 1asB will not be an integer matrix. But Es(B)Fs is always an integer matrix. This is a contradiction. So we must have a=±1 and thus B=±B.

    A square matrix A is decomposable if there exists a permutation matrix P such that PAPT is a block-diagonal matrix, and indecomposable otherwise.

    Lemma 3.2. Let 0B be an indecomposable skew-symmetrizable matrix. If B is obtained from B by a sequence of mutations and B=BA for some integer diagonal matrix A=diag(a1,,an), then A=±In and B=±B.

    Proof. If there exists i0 such that ai0=0, then the i0-th column vector of B is zero, by B=BA. This contradicts that B is indecomposable and B0. So each ai0 is nonzero for i0=1,,n.

    Let D=diag(d1,,dn) be a skew-symmetrizer of B. By B=BA and AD=DA, we know that

    BD=BAD=(BD)A.

    By the definition of mutation, we know that D is also a skew-symmetrizer of μk(B), k=1,,n. Since B is obtained from B by a sequence of mutations, we get that D is a skew-symmetrizer of B. Namely, we have that both BD and BD=(BD)A are skew-symmetric. Since 0B is indecomposable, we must have a1==an. So A=aIn for some aZ, and B=aB. Then by Lemma 3.1, we can get A=±In and B=±B.

    Lemma 3.3. Let B=diag(B1,,Bs), where each Bi is a nonzero indecomposable skew-symmetrizable matrix of size ni×ni. If B is obtained from B by a sequence of mutations and B=BA for some integer diagonal matrix A=diag(a1,,an), then aj=±1 for j=1,,n.

    Proof. By the definition of mutation, we know that B has the form of B=diag(B1,,Bs), where each Bi is obtained from Bi by a sequence of mutations. We can write A as a block-diagonal matrix A=diag(A1,,As), where Ai is a ni×ni integer diagonal matrix. By B=BA, we know that Bi=BiAi. Then by Lemma 3.2, we have Ai=±Ini and Bi=±Bi for i=1,,s. In particular, we get aj=±1 for j=1,,n.

    Lemma 3.4. Let A=A(x,B) be a cluster algebra, and f:AA be a Z-homomorphism of A. If there exists another seed (z,B) of A such that such that f(x)=z, then f(μx(x))=μf(x)(z) for any xx.

    Proof. After permutating the rows and columns of B, it can be written as a block-diagonal matrix as follows.

    B=diag(B1,B2,,Bs),

    where B1 is an n1×n1 zero matrix and Bj is nonzero indecomposable skew-symmetrizable matrix of size nj×nj for j=2,,s.

    Without loss of generality, we assume that f(xi)=zi for 1in.

    Let xk and zk be the new obtained variables in μk(x,B) and μk(z,B). So we have

    xkxk=ni=1x[bik]+i+ni=1x[bik]+i,andzkzk=ni=1z[bik]+i+ni=1z[bik]+i.

    Thus

    f(xk)=f(ni=1x[bik]+i+ni=1x[bik]+ixk)=ni=1z[bik]+i+ni=1z[bik]+izk=ni=1z[bik]+i+ni=1z[bik]+ini=1z[bik]+i+ni=1z[bik]+izk.

    Note that the above expression is the expansion of f(xk) with respect to the cluster μk(z). By

    f(xk)f(A)=AZ[z±11,,(zk)±1,,z±1n],

    we can get

    ni=1z[bik]+i+ni=1z[bik]+ini=1z[bik]+i+ni=1z[bik]+iZ[z±11,,z±1k1,z±1k+1,,z±1n].

    Since both ni=1z[bik]+i+ni=1z[bik]+i and ni=1z[bik]+i+ni=1z[bik]+i is not divided by any zi, we actually have

    ni=1z[bik]+i+ni=1z[bik]+ini=1z[bik]+i+ni=1z[bik]+iZ[z1,,zk1,zk+1,,zn].

    So for each k, there exists an integer akZ such that (b1k,b2k,,bnk)T=ak(b1k,b2k,,bnk)T. Namely, we have B=BA, where A=diag(a1,,an). Note that B has the form of

    B=diag(B1,B2,,Bs),

    where B1 is an n1×n1 zero matrix and Bj is a nonzero indecomposable skew- symmetrizable matrix of size nj×nj for j=2,,s. Applying Lemma 3.3 to the skew-symmetrizable matrix diag(B2,,Bs), we can get aj=±1 for n1+1,,n. Since the first n1 column vectors of both B and B are zero vectors, we can just take a1==an1=1. So for each k, we have ak=±1 and

    (b1k,b2k,,bnk)T=ak(b1k,b2k,,bnk)T=±(b1k,b2k,,bnk)T.

    Hence,

    ni=1z[bik]+i+ni=1z[bik]+ini=1z[bik]+i+ni=1z[bik]+i=1.

    Thus we get

    f(xk)=ni=1z[bik]+i+ni=1z[bik]+ini=1z[bik]+i+ni=1z[bik]+izk=zk.

    So f(μx(x))=μf(x)(z) for any xx.

    Lemma 3.5. Let A=A(x,B)F be a cluster algebra, and f be an automorphism of the ambient field F. If there exists another seed (z,B) of A such that f(x)=z and f(μx(x))=μf(x)(z) for any xx. Then

    (i) f is an automorphism of A;

    (ii) f is a cluster automorphism of A.

    Proof. (ⅰ) Since f is an automorphism of the ambient field F, we know that f is injective.

    Since f commutes with mutations, we know that f restricts to a surjection on X, where X is the set of cluster variables of A. Because A is generated by X, we get that f restricts to an epimorphism of A.

    Hence, f is an automorphism of A.

    (ⅱ) follows from (ⅰ) and the definition of cluster automorphisms.

    Theorem 3.6. Let A be a cluster algebra, and f:AA be a Z-algebra homomorphism. Then f is a cluster automorphism if and only if there exist two clusters x and z such that f(x)=z.

    Proof. "Only if part": It follows from the definition of cluster automorphism.

    "If part": It follows from Lemma 3.4 and Lemma 3.5.

    This project is supported by the National Natural Science Foundation of China (No.11671350 and No.11571173) and the Zhejiang Provincial Natural Science Foundation of China (No.LY19A010023).

  • This article has been cited by:

    1. Saoussen Boujelben, Nermine Medhioub, Does the combined assurance model affect tax avoidance? The case of South African companies, 2024, 1472-0701, 10.1108/CG-08-2023-0346
    2. Lorenzo Ligorio, Fabio Caputo, Andrea Venturelli, Sustainability reporting in public–private hybrid organisations: a structured literature review, 2024, 0967-5426, 10.1108/JAAR-06-2023-0178
    3. Precious T. Ngobeni, Leon Barnard, Mosie C.C. Molate, Enhancing the criteria for financial assistance to state-owned companies, 2023, 16, 2312-2803, 10.4102/jef.v16i1.881
    4. Jamie-Leigh Bruce, AC Neethling, J. Dubihlela, Adoption of Combined Assurance Within Supply Chain Management in the Cape Winelands District of South Africa, 2024, 5, 2700-8983, 288, 10.51137/ijarbm.2024.5.1.14
    5. Adeyemi Adebayo, Barry Ackers, Olayinka Erin, Examining the Extent of Compliance on Combined Assurance Reporting Quality: Evidence from Namibian State-owned Enterprises, 2024, 28, 1982-7849, 10.1590/1982-7849rac2024240173.en
    6. Rene Guimaraes Andrich, Liliane Cristina Segura, Combined assurance: Avaliando relatórios financeiros de forma integrada, 2025, 12, 3085-8526, e0163, 10.37497/jsim.v12.id163.2025
    7. Adeyemi Adebayo, Barry Ackers, Comparing innovative alternative assurance practices in emerging markets, 2025, 0210-2412, 1, 10.1080/02102412.2025.2515722
  • Reader Comments
  • © 2006 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(5400) PDF downloads(270) Cited by(43)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog