《Lecture-网络建模.ppt》由会员分享，可在线阅读，更多相关《Lecture-网络建模.ppt（59页珍藏版）》请在三一办公上搜索。
1、1,Complex NetworksInternet-Topology and Modeling,Instructor:G Ron Chen,网络建模（互联网）,2,Internet,Internet is a global system of interconnected computer networks that use the standard Internet Protocol Suite(TCP/IP)to serve billions of users worldwide(Wikipedia)Structure:Autonomous Systems(AS)Wide Area Ne
2、twork(WAN)Metropolitan Area Network(MAN)Local Area Network(LAN)Software:Transmission Control Protocol(TCP)Internet Protocol(IP)Other protocols at the application level:Internet Control Message Protocol(ICMP)File Transfer Protocol(FTP)Simple Mail Transfer Protocol(SMTP),3,Internet is a network of net
3、works(structure),Internet is the inter-connections of networks:Internet Service Provider(ISP)networksCorporate networks(e.g.Cisco and Microsoft)Campus networks(e.g.CityU)Mobile operator networks(e.g.one2free)Government networksInternet Exchanges(e.g.HKIX)through optical fibers(telephone lines),4,5,A
4、 Typical Application Example-Facebook,www.bbc.co.uk,Data Source,6,Protocols,Protocol originates from the Greek word protocollon,which was a piece of paper glued to a manuscript to describe its contents.In computing and communication systems,a protocol is a set of rules,a convention,or a standard,tha
5、t controls the connection and data transfer between endpoints.Telecommunication systems:data interchange protocols at the hardware device leveldata interchange protocols at the application program levelInternet:Transmission Control Protocol(TCP),for exchanging messages with other Internet points at
6、the information packet levelInternet Protocol(IP),for sending and receiving messages at the Internet address levelOther protocols:Hypertext Transfer Protocol(HTTP),File Transfer Protocol(FTP),Border Gateway Protocol(BGP),and Dynamic Host Configuration Protocol(DHCP),.,7,Brief History of the Internet
7、,1968-DARPA(Defense Advanced Research Projects Agency)contracts with BBN(Bolt,Beranek&Newman)to create ARPAnet1970-First five nodes:UCLA,Stanford,UC Santa Barbara,U of Utah,BBN1974-TCP specification by Vint Cerf1984-January 1,1984,the Internet with its 1000 hosts converts altogether to using TCP/IP
8、for its messaging,8,Earlier History of Internet,DARPA,9,Internet today,Host count is 768,913,036 in 2010 93,047,785 in 2000,826.36%,Data Source,10,11,Recent Internet Statistics,12,Recent Internet Statistics,13,Recent Internet Statistics,14,Recent Internet Statistics,World Population:7,100,000,000Num
9、ber of Users:2,400,000,000Internet backbone traffic grew from one Tbit/sec in 1990 to 3,000 Tbit/sec in 1997.It grew 40%in 2012 aloneNumber of Internet hosts more than doubled every year between 1980-2000China(in millions):CNNICInternet users:538Broadband subscribers:450IPv4 Addresses:330Domain Name
10、s:87.3International Bandwidth:1,548,811 Mbps,15,Netcraft-an Internet services company based in Bath,England,providing web server and web hosting market-share analysis,including web server and operating system detection.,16,It is governed by ICANN,Internet,17,Internet,IP,Hari Balakrishnan,It is gover
11、ned by ICANN,18,Internet,Backbone(2001):27.9%-UUNET/WorldCom/MCI10.0%-AT&T6.5%-Sprint6.3%-Genuity4.1%-PSINet3.5%-Cable&Wireless2.8%-XO Communications2.6%-Verio1.5%-Qwest1.3%-Global Crossing,EGP Exterior Gateway ProtocolIGP Interior Gateway Protocol,19,20,ASes typically connect at all hubs.,UUNET was
12、 founded in 1987:one of the largest Internet service providers and one of the nine Tier-1 networks,21,Internet at the AS Level,Internet at the Autonomous Systems(AS)level(Faloutsos brothers,1999),22,Internet at the AS Level,(Steve Uhlig),23,Internet at the AS Level,(Steve Uhlig),24,Internet Visualiz
13、ation,(2010)CAIDA Topology Mapping Analysis Team,25,Internet Visualization,North American Internet Backbone Has 134,855 Routers IP addresses(router level),1998 1999,(William R.Cheswick),26,27,Internet Topology Generators,Three stages of development:First generation includes:random topology generator
14、s(in 1980s);representative-Waxman generatorSecond generation includes:structural topology generators(in 1990s);representatives-Tiers and Transit-Stub generators(with hierarchical structures)Third generation(since 2000),based on node degrees;representatives-BRITE and Inet,small-world and especially s
15、cale-free network models IRL UCLA-Internet Topology Collection,28,Internet Topological Properties,Real AS-level Internet data can be obtained from the website of the Oregon Router Views Project,which was managed by the National Laboratory for Applied Network Research(NLANR),expired at the end of 200
16、6,and now managed by the Cooperative Association for Internet Data Analysis(CAIDA)This website is being updated within hours daily by taking snapshots from the routing tables of the Border Gateway Protocol(BGP),29,Internet Topological Properties,Other useful data about the AS-level Internet:Skitter
17、provides Internet topological measures by the CAIDA,using Traceroute(a computer network tool for determining the route taken by packets across an IP network.Whois is a domain search tool and data base,identifying the owners and IP addresses of all domains,but it is not automatically managed.RIPE NCC
18、 supports the infrastructure of the Internet and provides global Internet resources and related services(IPv4,IPv6 and AS Number resources)in Europe,Middle East and parts of Central Asia.,30,Real AS-Level Internet Data,Numbers of Internet AS(Nov.1997 Feb.2002)(Siganos et al.,2003),31,Power-Law Node-
19、Degree Distributions,Faloutsos M,Faloutsos P,Faloutsos C.On power-law relationships of the Internet topology.ACM SIGCOMM Computer Communication Review,1999,29(4):251-262,The Faloutsos Brothers,32,Power-Law Node-Degree Distribution,Power law:,where is the degree of node v,is the index of node v in th
20、e degree-decreasing ordering of all nodes,and is a rank constant exponent.,33,Internet Hierarchical Structures,Internet consists of a large number of interconnected ASAS may be considered as a Stub domain or a Transit domainTransit domain can be a Metropolitan Area Network(MAN)or a Wide Area Network
21、(WAN),typically a regional or even a national Internet Service Provider(ISP)Stub domain consists of campus networks or some other interconnected Local Area Networks(LAN)Transit domain is used to link many nearby Stub-domains togetherStub domain usually only processes the information starting and end
22、ing inside the domain,while a Transit domain has no such restriction,34,Internet Hierarchical Structures,AS-level Internet structure(Jaiswal et al.,2004),35,Internet Hierarchical Structures,AS-level Internet on 3 December 1998(generated by Skitter),36,Internet Hierarchical Structures,AS on the Inter
23、net can be considered as some kind of TierAn AS at the highest Tier belongs to the Transit domain,called Tier-1 provider,Those Transit and Stub domains at a lower Tier depend on the Transit nodes at a higher Tier to communicate with the other domains at their same level(Cai et al.,2004),37,Internet
24、Hierarchical Structures,Degree distribution of the AS-level Internet at different tiers(Jaiswal et al.,2004),38,Core layer,Distribution layer,Access layer,3-Tier Structure of the CTNET(HK CityU Campus Network,1985-),OCIO Newsletter,Jan 2011,39,A Breakthrough:Scale-Free Model“Emergence of scaling in
25、random networks”Science 286:509(1999),A.-L.Barabsi,R.Albert,(Norte Dame University),40,BA Scale-Free Network Model,(ii)Add new edges:The way to add the new edges into the network:Every existing node is to be chosen with probability,(i)Add new nodes:Add 1 new node into the network:This node is connec
26、ted to()existing nodes simultaneously,Start with a fully-connected network having nodes,41,Limitation of most scale-free Internet models,Preferential Attachment:,They all use global preferential attachment-Every newly added node requires the connectivity information of all nodes in the network A rea
27、l network only uses local preferential attachment with information of only some nodes in the network,(or,its variants),42,Question:How to describe a topology of the AS-level Internet with localization property?,The Internet consists of several sub-networks:each sub-network is called a“local-world”Th
28、e newly added node only needs connectivity information of those nodes in a local-worldThe connections among different local-worlds are sparseThe connections of nodes within the same local-world are dense,43,Our Scale-Free Network Model-Multi-Local-World(MLW)Model,This model includes 5 events:,Additi
29、on of local-worlds Addition of new nodes to local-worlds Addition of edges of new nodes to local-worlds Deletion of edges within a local-world Addition of edges among local-worlds,Oregon data(1998),44,MLW Model,45,Illustration of a Resultant Network,46,Internet Models at the AS-level:,Waxman model,T
30、ransit-stub model,Fluctuation-driven model BA model Generalized BA(GBA)model Fitness model HOT model,Poisson distribution,Power-lawdistribution,Evaluating the Internet models,47,Fluctuation-driven model-BA model Generalized BA(GBA)model Fitness model HOT model,Exponentially growing network,Linearly
31、growing network,Evaluating the Internet models(cont.),48,Fluctuation-driven model is NOT suitable for the AS-level Internet,Data(from 2004 to 2010),Number of Nodes,Linearly growing network,Evaluating the Internet models(cont.),49,Power Exponent:r=2.2 for real Internetr=3.0 for BA modelr=1.5 for HOT
32、model,BA and HOT models can NOT capture the scale-free feature of the Internet,Internet snapshot on May 15,2005,Evaluating the Internet models(cont.),50,Distance distributions of the Internet and of different scale-free models,Evaluating the Internet models(cont.),51,Clustering coefficients as funct
33、ions of the degree for the real Internet and the BA,GBA,Fitness,HOT,and MLW models.,BA,GBA,Fitness,and HOT models can NOT capture the small-world feature of the real Internet,Evaluating the Internet models(cont.),52,Comparison of the average shortest path-lengths in the giant component for the real
34、Internet and the five models studied.,Evaluating the Internet models(cont.),53,Evaluating the Internet models(cont.),Comparison:Four Models vs Real Internet,54,Comparison of MLW Model with other models,MLW model is better than the BA,GBA,and Fitness models in capturing the scale-free and small-world
35、 features of the Internet,55,Summary-MLW model is better than BA,GBA,Fitness,and HOT models in capturing the scale-free and small-world features of the InternetTopological Statistics-degree distribution,power-law exponent,distance distribution,clustering coefficient,average shortest path-length,hier
36、archical clustering But what about performances?,Further Evaluating the Internet models,56,Robustness against random attacks,:the size of the largest component after a fraction of nodes,f,in the network are randomly removed.,measures the capability of the network in which nodes still can communicate
37、 each other after the f portion of nodes has been randomly removed.,Comparison:What about performances?,Performance comparisons,T(r)-the ratio of the traffic load of the first r largest nodes over the total traffic load of the whole network,Traffic load distribution,MLW does not perform well,58,Conc
38、lusions,MLW is the best model for the AS-level Internet as compared to Fluctuation-Driven,BA,EBA,and Fitness models These comparisons were performed only based on part of the Internet features:degree distribution distance distribution average path-length clustering coefficient robustness against random attack The MLW model is rather complicated and not good in data trafficMore comparisons are neededInternet is too complex to comprehend.As of today,there is no commonly-agreed model of the Internet.Good models are badly needed,59,End,
