首页 > 代码库 > [Network]Network Layer
[Network]Network Layer
1 Introduction
1.1 Forwarding
Move pkts from router‘s input to appropriate router output.
1.2 Routing
The trip from source to destination1.3 Service Model
This is similar with other layers. The services consist of short delay, bandwidth or some thing else.
2 Connection
And I‘d like to mention that, datagram is used in IP and VC used in ATM for strict timing and reliability requirement.First I‘d like to compare with transport layer. The connection service of Internet layer:1) host-to-host2) Implement in Network core. (parse by routers)Then the connection part of Internet Layer is divided into:1) connection2) connection-less2.1 Virtual Circuit - connection service
This type of service is about building connection for each link and data transferring. The router will keep the connection state information of each link. When a packet of a link transferring, its carried VC number(built in the connecting process) helps the packet forwarded into exact outgoing. So the router keep the state with the VC numbers.As a result, this connection-based Internet Service is much similar with TCP I talked above.2.2 Datagram Networks - connection-less service
The packets forwarded using the destination host address.The mapping from address to interface may just take the high bits of address for a interface.
3 Router Architecture
The buffers of Input and Output both have the problem of overflowing, it will caused delay or loss.Forwarding(Switching) and Routing are most important parts of Router architecture.As we can see from the picture above. The switching unit is used to switch a packet from input port to output port physically. And the Routing processor seems to calculate the most adequate paths for input packets.3.1 Input port
1. line termination: bit-level reception2. data link: it is about link layer3. forwarding queue: lookup output port using forwarding table in input memory.3.2 Swithing fabric
Using memory, bus, crossbar.memory and bus, one packet at one time.3.3 Output port
Buffer is used to deal with the discordance between forwarding and transmission.
4 Routing Algorithm
4.1 Classification
Global or LocalStatic or Dynamic4.2 Link State
Dijsktra AlgorithmDO NOT calculate within translation, we can update in some time period.
4.3 Distance Vector
Bellman-Ford Equation
Information of One Node x1) the shortest cost from x to every node in the graph, D2) the cost from x to each neighbor of x, d3) the shortest cost from x‘s neighbors to every node in the graphThen use B-F Equation1) local link cost change2) DV messages from neighborsExample situation
Get the DVs from neighbors
Update its own DV (DO NOT change the neighbors DVs here, just itself)
Cost change -> news travel
Good news travel fast
The change happen in the critical way, so the news transfers fast because this way continue to be used.
Bad news travels slow
z wants to get x through y, but y tells z through it the way is long. So y and z tell again and again.
4.4 Hierarchical Routing
======
So put the Network into ASs. In the intra-AS, use intra routing algorithm. To other AS, through gateway router directly link to router in other AS.Example for Inter-AS Routing Algorithm
First add a AS x into the network
Since the routers in AS1 must get x through AS3. So the routers must update their forwarding tables to fit this.At this time, the router like 1d must determine how to get AS x, through AS3 or AS2. It is the job of inter-AS routing algorithm.Hot potato routing
1) Get the multiple gateways from 1d to AS3 and AS2 which make it accessible to x.2) Hot: choose the gateway that has smallest cost from 1d to.
5 Routing Protocol
5.1 Intra-AS Routing: Interior Gateway Protocols(IGP)
1. RIP: Routing Information Protocol
DV Algorithm: advertisement(exchange every 30s, each ad is a list of up to 25 destination subnets within AS)ad sent in UDPLink Failure: no ad heard for 180 sec -> the neighbor is deadRecovery: prevent ping-pong loops (infinate distance = 16 hops)Implement: RIP routing table is managed by application-level process, so RIP is considered as a application-layer protocol
2. OSPF: Open Shotest Path First
LS Algorithm: advertisements over directly IP (rather than TCP or UDP)Hirarchical OSPF: router keep the information it needboudary routersbackbone routersarea border routers
5.2 Inter-AS Routing
To sum up the Inter-AS Routing, especially BIG, Inter-AS Routing is supposed to control the routing paths in the network between multiple ASs. It use reliable connection to advertise new dests or new paths to other ASs. And each ASs(‘gateway router) will record these prefixes and paths. When some datagram transferring, the routers will take BGP messages to build connection and transfer data according to the prefix and path.1. BGP: Border Gateway Protocol
Service provided:1) Obtain subnet information of neighboring ASs2) Propogate Information to all AS-internal routers3) Detemine good routes to subnetsExchange information:1) TCP connections: routers exchange routing information over semi-permannent TCP connections -BGP sessionseBGP session: external, e.g. 3a-1ciBGP session: internal, e.g. 1c-1b2) prefix: When AS2 advertise a prefix to AS1, AS2 promises it will forward datagram to that prefix.The prefix can be transferred through eBGP or iBGPPath AttributesThis is advertised with prefix, prefix + attributes = “route”1) AS-PATH: ASs has been passed2) NEXT-HOP: internal-AS router to next ASBGP route selection1) local preference: policy decision2) shortest AS-PATH: advertised with prefix before3) Closest NEXT-HOP router: hot potato routingBGP messages: via TCP connection1) OPEN: TCP2) UPDATE: advertise a new path3) KEEPALIVE: TCP connection4) NOTIFICATION: error notification, close connection
6 Internet Protocol
6.1 Internet Network Layer
IP Layer is not just about how to forward datagram. It also consists of error detection and some packet handling process. And some datagram format is defined in the protocols.6.2 Datagram
1. Format
1) The second line is about IP datagram segmentation2) The third line is remaining time and checksum2. IP Fragmentation&Reassembly
Because nework link have MTU - largest link-level frameFragmentation
1) different link, different MTU2) reassembly only at final destinationExample
offset = length / 8
identification:在datagram建立的时候就赋予了一个号码,分割的时候这个号码不变
flags:最后一个子fragment是0,别的都是1
offset:在原来大的datagram中的位置
6.3 IPv4 addressing
1. CIDR: classless Inter Domain Routing
format: a.b.c.d/x2. DHCP: Dynamic Host Configuration Protocol
At the beginning, the client does not have a address. It broadcast the request "DHCP discover" for a IP address. If a DHCP server receives it, it response with a "DHCP offer" within which there is a address for the client. And the client transmits a formal "DHCP request" to the DHCP server. Then the server gets back a "DHCP ACK" at last. It afour handshake.
3. Get a block of IP addresses
ICANN: Internet Corperation for Assigned Names and Numbers.4. NAT: a trick for IP addressing
The main idea of NAT is transfer (NAT addr, NAT port) with (source addr, source port)
6.4 ICMP: Internet Control Message Protocol
6.5 IPv6
特点(1) 地址空间的扩展(2) 40 bytes 的头部(3) Flow labeling and priority头部(1) First 4 bytes: Version - Traffic class(TOS in IPv4) - Flow label(需要提供一些特别的服务,比如一些packets必须按相同的path传输,这样他们就不会乱序)(需要继续学习IPv6的头部)(2) Second 4 bytes: Payload length - Next header(protocol field in IPv4, TCP or UDP for example) - Hop limit(TTL in IPv4)(3) 128 bits: Source address(4) 128 bits: Destination address(5) dataIPv4在IPv6中没有了的内容(1) Fragmentation / Reassembly: 在IPv6中,不允许中间的router来进行分片操作,如果它们发现fragment太大,那么就发送一个ICMP报文回去。这样做的原因是:分片操作是一个耗时的操作,这样做可以加快转发的速度。(2) Header checksum:每次router都需要计算check sum(因为每次TTL都发生了变化),非常耗时。(怎么保证数据的正确性)(3) Option:在IPv6中再没有。因为可以让next header域指向data中的options。IPv4转换IPv6Tunneling:在IPv6的网路中,如果出现了IPv4的router,那么将IPv6作为payload放在IPv4的datagram里
7 Broadcast and Multicast Routing
7.1 In-network Duplicate
1. flooding:
send pkts to all the neighbors
2. controlled flooding:
broadcast just if the pkts have not broadcast before, each node keep a list of broadcasted pkts IDs.3. spanning tree:
1) build a tree first2) broadcast happened just in the tree traces7.2 Muticast Tree
1. Source-Based Tree: one tree per source
Shortest Path Tree: Dijkstra‘s AlgorithmReverse Path Forwardingpruning in Reverse Path Forwarding Tree: no need to forward datagrams down the subtree with no group member.
2. Group-Shared Tree: group uses one tree
minimal spanningNP-complete problemcenter-based tree: one router identified as center of the tree
Forward to center.
3. Internet Multicasting Routing: DVMRP - distance vector multicast routing protocol
flood and prune: reverse path and forwardingsource-based tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。