網(wǎng)絡(luò)實(shí)驗(yàn)計(jì)算機(jī)網(wǎng)絡(luò)

1、Computer NetworksLecture 12Wei Liu (劉威)Dept. of Electronics and Information Eng.Huazhong University of Science and TechnologyDec. 2011 Problem in Chapter4:There Is More Than One Network-2-3-Real case of Global InternetThe tree structure of the Internet in 1990169.229.131.81130.160.4.128The universit

2、ies can allocate the IP addresses for internal users freely = utilization of address spacerouting cost = link utili.routing cost = delayThe ISPs can have different optimal view of routing= Autonomous SystemClassful AddressingIn the olden days, only fixed allocation sizesClass A: 0*Very large /8 bloc

3、ks (e.g., MIT has 18.0.0.0/8)Class B: 10*Large /16 blocks (e.g,. Princeton has 128.112.0.0/16)Class C: 110*Small /24 blocks (e.g., AT&T Labs has 192.20.225.0/24)Class D: 1110*Multicast groupsClass E: 11110*Reserved for future useThis is why folks use dotted-quad notation!4CIDR: Hierarchal Address Al

4、location512.0.0.0/812.0.0.0/1612.254.0.0/1612.1.0.0/1612.2.0.0/1612.3.0.0/16:12.3.0.0/2412.3.1.0/24:12.3.254.0/2412.253.0.0/1912.253.32.0/1912.253.64.0/1912.253.96.0/1912.253.128.0/1912.253.160.0/19:Prefixes are key to Internet scalabilityAddress allocated in contiguous chunks (prefixes)Routing prot

5、ocols and packet forwarding based on prefixesToday, routing tables contain 200,000 prefixes (vs. 4B)-6-Lecture 12Chapter 4. InternetworkingProblem: There Is More Than One Network 4.1 Simple Internetworking (IP) 4.2 Routing 4.3 Global Internet 4.3.1 Subnetting 4.3.2 Classless Routing (CIDR) 4.3.3 Int

6、erdomain Routing (BGP) 4.3.4 Routing Areas 4.3.5 IP Version 6 (IPv6) -7-4.3.3 Interdomain Routing (BGP) Internet and Autonomous SystemInterdomain RoutingPath-vector routingBGP-8-Path-Vector RoutingExtension of distance-vector routingSupport flexible routing policiesAvoid count-to-infinity problemKey

7、 idea: advertise the entire pathDistance vector: send distance metric per dest dPath vector: send the entire path for each dest d321d“d: path (2,1)”“d: path (1)”data trafficdata traffic-9-Faster Loop DetectionNode can easily detect a loopLook for its own node identifier in the pathE.g., node 1 sees

8、itself in the path “3, 2, 1”Node can simply discard paths with loopsE.g., node 1 simply discards the advertisement321“d: path (2,1)”“d: path (1)”“d: path (3,2,1)”-10-Flexible PoliciesEach node can apply local policiesPath selection: Which path to use?Path export: Which paths to advertise?ExamplesNod

9、e 2 may prefer the path “2, 3, 1” over “2, 1”Node 1 may not let node 3 hear the path “1, 2”231231-11-4.3.3 Interdomain Routing (BGP) Internet and Autonomous SystemInterdomain RoutingPath-vector routingBGP-12-Interdomain routing protocol for the Internet Prefix-based path-vector protocolPolicy-based

10、routing based on AS PathsEvolved during the past 18 years1989 : BGP-1 RFC 1105, replacement for EGP1990 : BGP-2 RFC 11631991 : BGP-3 RFC 12671995 : BGP-4 RFC 1771, support for CIDR 2006 : BGP-4 RFC 4271, updateBorder Gateway Protocol-13-Features of BGPAllows ASes to tell other ASes about “routes” (p

11、arts of the IP address space) that they are “responsible” for and how to reach themCommuniation by BGP-speakerUsing “route advertisements”, or “promises” - also called “NLRI” or “network-layer reachability information”P(pán)ath-vector routing protocolPolicy-based: allow ISPs to richly express their routi

12、ng policy, both in selecting outbound paths and in announcing internal routes Relatively “simple” protocol, but configuration is complex-14-BGP OperationsEstablish session on TCP port 179Exchange all active routes Exchange incremental updatesAS1AS2While connection is ALIVE, exchange route UPDATE mes

13、sagesBGP sessionrouter A129.213.1.2router B129.213.1.1-15-Incremental ProtocolA node learns multiple paths to destinationStores all of the routes in a routing tableApplies policy to select a single active routeIncremental updatesAnnouncement Upon selecting a new active route, add node id to path and

14、 (optionally) advertise to each neighborWithdrawalIf the active route is no longer available send a withdrawal message to the neighbors-16-SummaryPath-vector routingFaster convergence than distance-vector protocolsWhile hiding information and enabling flexible policyInterdomain routingAutonomous Sys

15、tems (ASes)Policy-based path-vector routing-17-Lecture 12Chapter 4. InternetworkingProblem: There Is More Than One Network 4.1 Simple Internetworking (IP) 4.2 Routing 4.3 Global Internet 4.3.1 Subnetting 4.3.2 Classless Routing (CIDR) 4.3.3 Interdomain Routing (BGP) 4.3.4 Routing Areas 4.3.5 IP Vers

16、ion 6 (IPv6) -18-4.3.4 Routing AreasAn area is a set of routers that are administratively configured to exchange linkstate information with each otherArea Broad Router(ABR)summarize routing information that they have learned from one area and make it available to other areas.All the routers in the a

17、rea send link-state advertisements to each other, and thus develop a complete, consistent map of the areaArea 0 is the backbone area for crossing areas-19-4.3.4 Routing AreasTradeoff between scalability and optimality of routingAll packets traveling from one area to another to go via the backbone ar

18、ea, even if a shorter path might have been availableTradeoff between scalability and optimality of addressingHierarchy addressing hindering the ability to make perfectly optimal decisions. However, it is essential to scalability which saves all nodes from having global knowledge. Important principle

19、 in network designScalability is a more pressing design goal than perfect optimality in large networks-20-Lecture 12Chapter 4. InternetworkingProblem: There Is More Than One Network 4.1 Simple Internetworking (IP) 4.2 Routing 4.3 Global Internet 4.3.1 Subnetting 4.3.2 Classless Routing (CIDR) 4.3.3

20、Interdomain Routing (BGP) 4.3.4 Routing Areas 4.3.5 IP Version 6 (IPv6) -21-4.3.5 IP Version 6 (IPv6) Initial motivation: IPv4 addresses are running outinherent problem of IPv4 addressing:no 100% address assignment efficiencygranularity of network sizeproliferation in the number of networksgrowth in

21、 the number of devices with access to the InternetAdditional motivation:header format helps speed processing/forwardingheader changes to facilitate QoS Expanded address space: 128-bit-22-IPv6 Address Space128-bit address means 2128 (approximately 3.4x1038) addressescompared with IPv4, 1029 times mor

22、e addresses7x1021 addresses per m2Reason of such a large address spaceimpossible to achieve 100% efficiency of address assignmentPlenty bits for hierarchical addressingAllow simple and flexible autoconfigurationHas no classesSubdivided based on the leading bits-23- IPv6 Address Space AllocationAn ex

23、ample of reserved address: patible IPv6 addressthe last 32 bits contains an IPv4 address, and the other bits are all 0PrefixUse0000 0000Reserved001Aggregatable global unicast addresses1111 1110 10Link local use addresses1111 1110 11Site local use addresses1111 1110Multicast addresses-24-IPv6 Address

24、 NotationBasic unit: 16-bit word in hexadecimalexample: the 16-bit word 0010 0111 1100 1101Leading zeros in a 16-bit word can be omittedExpressed with 8 16-bit words separated by colonexample: 47CD:1358:39CD:A37D:1845:2A3B:6479:DAEFA contiguous group of zeros can be suppressedexample: 47CD:1358:0:0:

25、0:0:6479:DAEF es 47CD:1358:6479:DAEF example: 47CD:0:0:A37D:0:0:6479:DAEF ? patible addressexample: :202.114.0.242-25-IPv6 Header Format128bit address128bit addressIPv4 fields disappeared in IPv6 header: header length, fragmentation, header checksumreplaces both option and protocol fields in IPv4; i

26、dentifies the type of immediately following header (either option or transport layer header)-26-Fragmentation by SourceIPv6 routers dont fragment packetsSource hosts are responsible to learn the smallest MTU supported along the routing pathsIf necessary, a source host fragments the message from the

27、upper layer, and adds fragmentation headerOtherwise, a source should limit packets to 1280 bytes-27-Extension HeadersFixed length of IPv6 header: 40 bytesIPv6 treats options as extension headersthe last extension header points to transport layer headerA number of extension headers have been defineds

28、hould appear in a specific order to simplify the processingenhance routing capabilities-28-Transition from IPv4 to IPv6The transition process is progressiveTwo problems-29-IPv6 Transition: Dual Stack An IPv6 router runs both IPv4 and IPv6solves problem 1-30-IPv6 Transition: IP Tunneling-31-Lecture 1

29、2Chapter 4. InternetworkingProblem: There Is More Than One Network 4.1 Simple Internetworking (IP) 4.2 Routing 4.3 Global Internet 4.3.1 Subnetting 4.3.2 Classless Routing (CIDR) 4.3.3 Interdomain Routing (BGP) 4.3.4 Routing Areas 4.3.5 IP Version 6 (IPv6) NAT: Network Address TranslationNAT: Networ

30、k Address TranslationMotivation: local network uses just one IP address as far as outside world is concerned:range of addresses not needed from ISP: just one IP address for all devicescan change addresses of devices in local network without notifying outside worldcan change ISP without changing addr

31、esses of devices in local networkdevices inside local net not explicitly addressable, visible by outside world (a security plus).-32-33-NAT: Network Address Translation10.0.0.110.0.0.210.0.0.310.0.0.4138.76.29.7local network(e.g., home network)10.0.0/24rest ofInternetDatagrams with source or destina

32、tion in this networkhave 10.0.0/24 address for source, destination (as usual)All datagrams leaving localnetwork have same single source NAT IP address: 138.76.29.7,different source port numbers-34-NAT: Network Address Translation10.0.0.110.0.0.210.0.0.3S: 10.0.0.1, 3345D: 128.119.40.186, 80110.0.0.4

33、138.76.29.71: host 10.0.0.1 sends datagram to 128.119.40.186, 80NAT translation tableWAN side addr LAN side addr138.76.29.7, 5001 10.0.0.1, 3345 S: 128.119.40.186, 80 D: 10.0.0.1, 33454S: 138.76.29.7, 5001D: 128.119.40.186, 8022: NAT routerchanges datagramsource addr from10.0.0.1, 3345 to138.76.29.7

34、, 5001,updates tableS: 128.119.40.186, 80 D: 138.76.29.7, 500133: Reply arrives dest. address: 138.76.29.7, 50014: NAT routerchanges datagramdest addr from138.76.29.7, 5001 to 10.0.0.1, 3345 -35-NAT: Network Address Translation16-bit port-number field: 60,000 simultaneous connections with a single L

35、AN-side address!NAT is controversial:routers should only process up to layer 3violates end-to-end argumentNAT possibility must be taken into account by app designers, eg, P2P applicationsaddress shortage should instead be solved by IPv6ReviewGlobal Internet: scaling problems the efficient use of add

36、ress space and the growth of routing hierarchical IP address formatSubnettingCIDRnew address format: IPv6autonomous systems: Path vector routing, BGP-36-37-Lecture 12Chapter 4. InternetworkingProblem: There Is More Than One Network 4.1 Simple Internetworking (IP) 4.2 Routing 4.3 Global Internet 4.4

37、Multicast4.5 Multiprotocol Label Switching (MPLS) 4.6 Summary -38-Unicast, Multicast, BroadcastUnicast: one-to-oneone host communicates with another hostBroadcast: one-to-allone host sends the same packets to all hosts on the networkMulticast: one/many-to-manya host sends the same packets to a selec

38、ted group of hosts on the network options: one-to-many, many-to-many-39-Applications: Unicast vs. MulticastSample applications which need one-to-many communicationmultimedia transmission, e.g., Internet radioTeleconferencingnetwork gamesBy unicast: 1 senders and n receiversneeds to send n packetsBy

39、multicast: 1 senders and n receiverssender needs to send 1 single packet to a multicast addressdownstream routers duplicate this packet and forward the counterparts over the links along which there exist receivers-40-Using UnicastSource -41-Using MulticastSource -42-Why MulticastEfficiency of networ

40、k resource utilizationUsing unicastload on the sender and first link: ntotal load: nd, in which d is the network diameterUsing multicastload on the sender and first link: 1total load: d log (n)-43-IP MulticastD class IP addresses (1110 x.x.x.x) are specified for multicast destinationsA packet is sen

41、t to a multicast addressBest effort deliveryDynamic membership of a multicast groupjoin and leave the group at willAny host can send packets at any timeincluding nonmember hosts-44-IP Multicast (contd.)Hosts join and leave a multicast group using Internet Group Management Protocol (IGMP)Network is r

42、esponsible to transmit the packets to the hosts which join a multicast groupmulticast routingRemainderaddress assignmentmapping application to group-45-Multicast Routing AlgorithmsObjectiveto determine a multicast tree based on the location of the recipients on the network Three mechanismssource-spe

43、cific tree: DVMRP, PIM-DMshared tree: PIM-SM, CBTlink state: MOSPFMulticast forwardingPackets are replicated when a branch splitsWhy Isnt Multicast Pervasive?(Reasonably) Sound technologyBut fairly complex, with several versions of protocolsImplemented in most routersUsed by some enterprisesBut not

44、deployed/used on public Internet-46-47-Possible ExplanationsLack of demand (up until now?)Lack of membership/sender controlMany services need it: who can join, who cannotAlso needed for billing, etc. Hard to implement sender controlCan be subject to (and used to amplify) DoS attackLack of multicast

45、addressglobal allocation requiredInter-domain issues:Violates current ISP settlement modelNo incentive for ISPs to enable multicast.-48-Lecture 12Chapter 4. InternetworkingProblem: There Is More Than One Network 4.1 Simple Internetworking (IP) 4.2 Routing 4.3 Global Internet 4.4 Multicast 4.5 Multip

46、rotocol Label Switching (MPLS) 4.6 Summary -49-Motivation of MPLSInitially developed to simplify packet forwarding process within a high-speed routerconventional IP router: destination-based, lookup with longest prefix matchreplacement: label-based, lookup with a fixed-length labelsimpler, faster: i

47、mportant especially in the design of high-speed routersCurrently panied with the concerns oftraffic engineeringquality of servicenetwork scalabilityvirtual private networks-50-Idea behind MPLSCombine datagram switching with virtual circuit switchingdatagram switching: flexible, robust, e.g., IPvirtu

48、al circuit switching: simple packet processing, e.g., ATMother features of them?Problem: how to run connectionless protocols (IP) over connection-oriented underlying networks?MPLS: divide the functionality into two distinct partspacket forwarding (data plane): label-basedroutes management (control p

49、lane): conventional IP routing protocols, or , are used to manage forwarding paths-51-Conventional IP Forwarding10.1.1/2410.3.3/2400110.1.1010.3.30 PrefixInterface10.1.110.3.30 PrefixInterface1R2R1R4R3-52-Changes by MPLS10.1.1/2410.3.3/24001R2R1R4R310.1. 1 010.3.3 0 PrefixInterface1510.1.1 11610.3.3

50、 0 LabelPrefixInterface1510.1.1 11610.3.3 0 LabelPrefixInterfaceLabel = 15, Prefix = 10.1.110.1.1/2410.3.3/2400110.1.1 010.3.3 0 PrefixInterfaceR2R1R4R3RemoteLabel1516(a)(b)-53-Changes by MPLS (contd.)(c)10.1.1/2410.3.3/24001R2R1R4R31510.1.11241610.3.30 LabelPrefixInterface10.1.1 010.3.3 0 PrefixInt

51、erfaceRemoteLabel1516RemoteLabelLabel = 24, Prefix = 10.1.1-54-LabelsLabelTTLExp.S4 bytesLabel: 20-bit value, (0-16 reserved)Exp.:3-bits Experimental ( ToS)S:1-bit Bottom of stackTTL:8-bits Time To LiveLayer 2 HeaderIP Packet.MPLS shim headersMPLS encapsulations are also defined for ATM and Frame re

52、lay.Header operationsSwap (label)Push (a new header)Pop (a header from stack)Label SwitchingLook up inbound label + port (+Exp)to determine outbound label + port + treatment-55-Partition of Routing and ForwardingRoutingForwardingOSPF, IS-IS, BGP, RIPMPLSForwarding TableBased on:Classful Addr. Prefix

53、?Classless Addr. Prefix?Multicast Addr.?Port No.?ToS Field?Based on:Exact Match on Fixed Length LabelBy separating Routing from forwarding MPLS introduces more flexibility to develop new routing solutions without impacting the data plane hardware of label switch routersSingle forwarding paradigm mul

54、tiple routing paradigmsThe edge LSR is able to use a wide variety of input in determining the FEC, and not just the destination IP addressFlexibility in forming FECs-56-Applications and Extensions of MPLSApplications include high-speed layer 3 switching, andtraffic engineeringquality of servicenetwork scalabilityvirtual private networksExtensionsMultiProtocol Lambda Switching (MPS) MPLS control of lightpaths/optical trailsGeneralized MPLS (GMPLS) MPLS control of packets, circuits, lambdas and ports-57-Lecture 12Chapter