Computer Networking A top-down approach 정리 5

Link layer

• host와 router는 node, node를 연결하는 통신 채널은 link
• link layer에 의해 교환되는 data의 단위를 frame이라하여, network layer의 datagram을 캡슐화한다.
• 오류검출, 재전송, 흐름제어, 랜덤 접속과 같은 기능을 수행한다.
• link layer protocol의 예로는 ethernet, 802.11, wifi, token ring, PPP, ATM 등이 있다.
• path상의 각 link에서 서로 다른 link layer protocol에 의해 datagram이 처리될 수 있다. 예를 들면 첫번째 link는 ethernet에 의해 처리되고, 두번째 link는 WAN protocol에 의해 처리될수 있다는 것이다.

* link layer가 제공하는 service는 link에 적용되는 특정 link layer protocol을 따른다. 

1. frame: network layer의 datagram을 link로 전송하기 전에 frame에 캡슐화 시킨다. 
2. link 접속: MAC(medium access control, 매체 접속 제어) link로 frame을 전송하는 규칙에 대해 명시. 언제 link에 frame을 전송할 수 있게 하는지에 대한 정책을 의미하는 듯.
3. reliable transmission: acknowledgment(확인응답), 재전송을 통해 신뢰적 전달을 수행.
   무선 링크처럼 오류율이 높은 link에서 주로 사용된다.
   transport layer 또는 application layer의 재전송 방식과는 달리 link layer protocol은 오류가 발생한 link에서 오류를 정정한다.  보통 대다수의 wired link layer protocol에서는 이 서비스를 제공하지 않는다.
4. flow control: link의 양단에 있는 node들은 제한된 frame buffer를 갖는다. frame 손실을 막기 위해서는 transport layer처럼 link layer들도 흐름제어를 제공할 수 있다.
5. 오류검출:오류 검출 비트를 이용함. link에서 오류검출은 보통 하드웨어로 구현됨.
6. 오류정정: 오류 검출과 오류를 정상적인 데이터로 수정한다.
7. half-duplex(반이중), full-duplex(전이중)

* link layer의 위치

대부분 link layer는 network adapter인 network interface card(NIC)에서 구현된다. 

* 오류 검출 및 정정 기술

* 다중 접속 프로토콜
link layer channel 에는 크게 두 종류가 있다.

1. broadcast channel: 근거리 network, wireless LAN, 위성 network 접속 네트워크에서 사용됨. 보통 다수의 host가 동일한 communication link에 연결된다. 따라서 host간의 전송을 조절하고, collision을 방지하기 위한 media access protocol이 필요하다
2. Point-to-point communication link: 두 router 또는 ISP router간에 사용될수 있다.

* broadcast link에서 다수의 hosts가 공유되는 broadcast channel을 이용하므로 multiple access problem(다중접속문제)이 발생한다. 두 개 이상의 host들이 frame을 전송하면 전송된 frame들이 수신자에서 충돌한다. 따라서 수신된 노드도 전송된 frame의 의미를 파악할 수 없게 된다.

1. channel partitioning protocol(채널 분할 프로토콜)
   channel이 N개 노드, 전송률이 R bps일때,
1. TDM(time division multiplexing, 시분할 다중화)
   시간을 time frame으로 나누도 각 time frame을 다시 N개의 time slot으로 나눈다. 각 time slot은 N개의 노드에게 각각 할당된다. 노드는 전송할 packet이 있으면 TDM frame에서 자신에게 할당된 time slot 동안 packet bit를 전송한다.
   단점: 전송할 packet이 있는 노드가 단 하나인 경우 노드 전송률이 평균 R/N으로 제한되며, 노드가 전송을 위해 자신의 차례를 기다려야만 한다.
2. FDM(frequency division multiplexing, 주파수분할 다중화)
   R bps의 channel을 R/N의 대역폭을 갖는 다른 주파수로 나누어 각 주파수를 N개의 노드에 할당한다.
   단점: 전송할 packet을 가진 노드가 하나있더라도 노드는 R/N의 대역폭으로 제한된다.
3. CDMA(Code Division Multiple Access, 코드분할 다중 접속): 서로 다른 코드를 각 노드에 할당하고, 노드는 전송하는 data bits를 자신의 유일한 코드로 인코딩한다. 때문에 전송시 여러 노드들에 의한 interfere가 일어나도 수신자들이 송신자의 코드를 알고 있다면 정확하게 수신할 수 있다.
2. random access protocol(랜덤 접속 프로토콜)
   노드는 항상 link의 최대 전송률인 R bps로 전송한다. collision이 생기면 관련된 각 노드는 frame(packet)이 collision 없이 전송 될때까지 자신의 frame을 계속 재전송 한다. 단 재전송시 일정 시간동안 기다렸다가 전송한다.
   channel이 N개 노드, 전송률이 R bps일때,


1. slotted ALOHA: 모든 frame이 L bit로 구성, time은 L/R, 노드는 slot의 시작점에서 frame을 전송한다. 각 노드는 언제 slot이 시작하는지 알수 있게 동기화되어 있다.
   p를 probability이라고 할때, 노드가 frame(packet) 전송시 collision이 발생하면 frame이 collision 없이 전송될 때까지 확률 p로 해당 frame을 다음 slot에서 재전송한다.
   단점: slot에 동기화 되어야 한다.
   효율성: packet을 보내는 active node가 많으면 collision이 발생한다. 확률적인 재전송으로 인해 전송을 하지 않는 경우가 발생하는데 이럴경우 낭비되는 slot이 발생한다.
   각 slot 마다 확률 p로 전송을 하고, N개의 node가 존재한다고 할때, 한개의 node만 전송하고, N-1개의 node는 전송하지 않아야 한다. 한 node가 전송할 확률은 p, N-1개의 노드가 전송하지 않을 확률은 (1-p)^(N-1) 이다. 따라서 주어진 한 node가 전송에 성공할 확률은 p*(1-p)^(N-1) 이며 노드가 총 N개 있으므로, N*p*(1-p)^(N-1) 이 된다. 이 식을 최대화 시키는 p를 구해야한다.
   0<p<1이고, N*p*(1-p)^(N-1)를 미분해서 결과를 0으로 잡고 풀면 p가 1/N일때 최대화가 된다. N*p*(1-p)^(N-1)에 p=1/N을 넣고, n이 무한대로 갈때의 극한을 취하면 1/e가 나온다.(1-1/N)^N의 극한은 1/e라고 친절히 책에 씌여 있다. 따라서 1/e는 0.37이므로, slotted ALOHA에서 nodes가 frame을 전송할때의 실제 전송률은 0.37*R bps가 된다. 즉, 100 Mbps로 전송 가능한 network에서 실제 처리율은 37 Mbps보다 낮게 된다.
                                  
2. pure ALOHA(=ALOHA)
   slot이 없고 완전히 분산된 protocol이다. frame이 도착하면(network layer의 datagram이 송신 노드의 network layer의 아래로 전달되면) 노드는 그 frame을 바로 broadcast channel로 전송한다. 만일 collision이 발생하면 호가률 p로 다시 보낸다.
   효율성: 앞에서 계산한 slotted ALOHA와 비슷한데 slot이 없으므로 각 node가 전송시 겹쳐지는 것을 고려해야 한다. (slot에서는 slot으로 맞춰져 있기 때문에 겹쳐지는 경우가 없다.) 따라서, N*p*(1-p)^(N-1)에다가 다른 노드가 전송을 시작하지 않을 확률 (1-p)^(N-1)을 고려하면, N*p*(1-p)^2(N-1) 가 된다. 효율은 1/(2e)이므로 slotted ALOHA의 절반이다.
                               
3. CSMA
   carrier sensing: node에서 frame 전송전에 channel에서 다른 node가 frame을 전송하는지 감지한다. 만일 다른 node가 frame을 전송하고 있다면, 임의의 시간동안 기다린 후 다시 channel을 감지한다.
   
   collision detection: node는 전송을 하면서 동시에 channel을 감지한다. 따라서 다른 node가 frame을 전송하면, 자신의 전송을 중단한다.
   
   만일 node가 타 nodes의 전송을 감지한다면 어떻게 collision이 발생하는가에 대한 질문은 간단하다. 전파 시간때문이다. A와 B노드가 서로 frame을 전송할때, A에서 B 사이에는 t시간이 지나야 서로에게 frame이 도착한다고 하면, A가 channel이 비어있어서 frame을 보낸후 t시간이후에 B가 보낸 frame을 감지할수 있게 된다. 이것이 channel propagation delay 이다.
4. CSMA/CD
   CSMA의 carrier sensing과 collision detection을 포함하며, ethernet을 사용한다.
   node들이 hub(link layer의 switch가 아님)에 연결되는 경우 ethernet LAN은 broadcast LAN이된다. 이때, 다중 접속 프로토콜이 사용된다.
   
   adapter가 network layer에게 datagram을 받아 frame으로 만든후 adapter의 buffer에 저장하고, channel이 idle하면(96bit 시간동안 channel로부터 adapter로 들어오는 신호가 없다면) frame을 전송한다. 만약 channel이 busy하면, 신호가 감지 되지 않을때까지 96bit 시간을 기다렸다가 frame을 전송한다. (계속 busy하면 계속 기다릴듯.) 전송하는 동안 다른 신호를 감지하면 frame 전송을 중단하고 48 bit jam(포기신호) 신호를 전송한다. jam 신호를 전송한후 adapter는 exponential backoff 단계로 들어간다. frame 전송시, n 번째 충돌을 경험한 adapter는 {0, 1, 2, ... 2^m-1} m=min(n,10)으로부터 k값을 선택하고, k*512bit 시간을 기다렸다가 재전송을 한다.
   간단히 말해서 충돌시, 1번 충돌하면 0,1 중 하나를 선택하여 그만큼 대기하다가 재전송, 2번째 또 충돌하면 0,1,2,3 중 하나를 선택하여 그만큼 있다가 재전송, 3번째면 0,1,2,3,4,5,6,7중 하나를 선택하여 그만큼 있다가 재전송 한다.
3. taking-turns protocol(순번 프로토콜) 
1. polling protocol: nodes중 하나를 마스터 node로 지정하고, 마스터 node는 라운드 로빈 방식으로 polling 한다. 즉, node 1이 전송한 후에 node 2가 전송하게 하고, 순서대로 차례차례 전송을 하게 조절해 주는 것이다.
   단점은 polling 지연(node가 전송할수 있음을 알리는데 걸리는 시간이다.)과 마스터 node의 고장이다.
2. token-passing protocol: token이라는 특수 목적을 가진 frame이 정해진 순서대로 node 간에 전달된다. node가 token을 받으면 전송할 frame이 있으면 전송하고, 없으면 다음 node로 넘긴다.
   단점은 node가 token을 놓지 않을때와 token packet이 사라지거나 손실될 경우이다.

* broadcast channel에서 다중 접속 프로토콜이 사용되며, 특히 근거리 네트워크인 LAN에서 사용된다.
LAN의 기술로 ethernet(랜덤 접속 기반), token ring(토큰 전달 방식), FDDI(Fiber Distributed Data Interface)이 있다. 


* link layer의 address system
network layer에서도 address를 가지며, link layer에서도 address를 가진다. IP address를 link layer address로 변환하는 대에는 ARP(Address Resolution Protocol)이 사용된다.

1. MAC address
   link layer의 address는 LAN address, physical address 또는 MAC address 라고 알려져 있다. 보통의 경우 MAC address는 6byte 이며, 2^48개의 사용가능한 주소가 있다. 6byte 주소는 보통 16진수로 표기되며, ROM에 박혀서 변경이 안되었지만, 요즘은 변경 가능한거 같다.
   MAC address는 계층 구조가 아닌 평면 구조이며, 전세계의 어떤 다른 device와 겹치지 않는다. MAC address에서 첫 24bit는 iEEE에서 고정시켰으며(아마 고유하게 회사마다 부여하겠지.), 나머지 24bit를 회사에서 각각의 device의 adapter에 고유하게 부여한다. IP address의 경우 host가 이동하면 변경되야한다. 하지만 MAC address 같은 경우 사람의 주민증록 번호와 같아서 바뀌지 않는다. (IP address는 사람이 현재 사는 집 주소, 이사가면 바뀐다. )
   
   adapter가 frame을 전송할 때는 frame에 destination MAC address를 넣고, LAN으로 전송한다. destination에서 수신된 frame은 일단 MAC이 자신의 것과 일치하는지 보고, frame에 있는 datagram을 추출하여 network layer로 올린다.
   송신 adapter는 frame의 destination address field에 특수한 MAC broadcast address를 넣어 다른 모든 adapter가 frame을 받게 할수도 있다. (broadcast address는 FF-FF-FF-FF-FF-FF의 형태이면 bit는 1이 48개 있는 형태이다.)
2. node가 IP address와 MAC address를 갖는이유
   네트워크 구조에서 계층이 독립적인 구성요소가 되게 하기 위해 각 layer들은 자신만의 address system을 갖아야 한다. adapter에서 고정적인 MAC address가 아닌 IP address를 사용하면 다른 network layer protocol을 쉽게 지원하지 못한다. 또한 IP address를 MAC address 대신 사용한다면, IP address를 RAM에 저장하고, adapter의 이동시 다시 설정하는 것이 필요하다.
3. ARP(Address Resolution Protocol)
   IP address와 MAC address 사이에서의 변환을 지원해준다.
   source host는 destination host의 IP address를 DNS를 통해 알아냈다고 하면, packet을 보낼때, desination host의 MAC address도 알아야한다. 이걸 알려주는 것이 ARP 이다.
   
   DNS와 비슷한 역할을 하지만 차이점은 DNS가 internet의 임의의 장소에 있는 host의 host name을 처리하지만, ARP는 동일한 LAN상에 있는 node의 IP address만을 처리한다는 것이다. 만일 서울에 있는 node가 부산의 node를 위해 ARP를 요청하면 ARP는 오류를 반환할 것이다.
   
   * 동작
   각 node(host or router)는 node의 RAM에 ARP table을 갖고 있다. 이 table에 IP address와 MAC address간의 mapping information이 있다. 또한 table에는 각 mapping information(entry) 마다 TTL(time-to-live) 값을 포함한다. 각 entry의 존재 시간은 table에 등록된 후 20분이다.
   node가 packet을 보낼때, 자신의 ARP table을 보고, mapping 된 MAC address가 있으면 사용하면 끝난다. 하지만 없는 경우 ARP protocol을 사용한다.
   송신 node는 송신 및 수신 IP address와 MAC address를 포함하는 field를 가진 ARP packet을 만들고 subnet 안의 다른 모든 node에게 query를 한다.
   이때 이용하는 것이 broadcast address(FF-FF-FF-FF-FF-FF)이다. 이 packet을 수신한 node는 packet안의 IP address가 가진과 일치하는지 검사하고, 일치하면 응답 ARP packet을 query한 node에게 보낸다. 이 응답 ARP를 받은 송신 node는 응답 ARP packet에서 MAC address를 알아내고, 자신의 ARP table을 갱신하고, packet을 destination으로 볼수 있게 된다. ARP table은 자동으로 구성된다.
   
   subnet에 없는 node로의 datagram 전송
   위에 설명된 경우와 다르게 a node가 속한 subnet에 없는 node에 packet을 보내는 경우가 있다. host는 router와 연결되었으며, 각 router의 interface는 ARP module과 adapter를 갖는다.
   host A에서 다른 subnet에 있는 host B로 packet을 전송시, 중간에 route가 하나만 있다고 가정. A는 먼저 자신의 subnet에 broadcast해보고 B가 subnet에 없음을 알아낸다.
   따라서, router로 packet을 보내야 한다. router의 MAC address는 ARP를 통해서 알아내고, host A는 router로 packet을 보낸다. 물론 packet의 destination MAC address는 최종 목적지 host B의 것이 아닌 router의 것이다. 안그러면 router가 자신에게 온 packet으로 판단하지 않고, 버린다.
   router로 도착한 packet은 router의 network layer로 datagram을 전달하고, 여기서 목적지 IP address를 확인한다. router는 routing table을 보고 적절한 interface로 내보낸다. 이때 적절한 interface는 router가 subnet에 query를 한다. packet의 destination IP address가 111 이면, subnet에 111이 누구냐고 broadcast하고, 응답이 오면 여기서 MAC address를 알아낸다. 그럼 MAC address를 이용하여 packet을 다시 조립하여 final destination으로 packet을 보낸다.
4. Ethernet
   고속 LAN, token ring, FDDI, ATM보다 싸다.
   hub 기반의 star topology를 사용하는 ethernet도 나옴. hub는 frame이 아닌 각 bit에 대한 처리를 하는 physical layer의 장치로 0과 1bit가 오면 energy의 세기를 증가시키고, 모든 interface로 전송한다. 후에 hub가 switch로 대체되었다.
   
   송신 adapter는 IP datagram을 ethernet frame에 캡슐화하고 physical link로 전송한다.
   ethernet frame: IP datagram이 있는 data field(46~1500 byte), destination address(6byte, 목적지 adapter의 MAC address), source address(6byte, 전송하는 adapter의 MAC address), type field, CTC(4byte), preamble(8byte, 수신 adapter의 클록을 송신자의 클록에 동기화 시킨다. frame의 전송되는 것을 잘 받기위해 사용하는 것인듯 하다.)
   
   ethernet 종류에 따라 여러가지 encoding방식이 있다 10Base-T는 Manchester encoding을 사용한다. 각 bit마다 1은 상위에서 하위로의 전위, 0은 하위에서 상위로의 전이를 갖는다. 이 것이 필요한 이유는 송신 및 수신 adapter들의 클록이 완벽하게 동기화 되어 있지 않아서 이다. 따라서, 수신 adapter의 클록이 동기화 되면, 수신자는 각 bit를 구분해서 그 bit가 1인지 0인지를 결정한다.
   
   최초의 ethernet의 문제는 전선의 저항으로 신호가 점점 약해진다는 것이다 이것은 hub로 신호를 키운다.

* bus topology, hub 기반 star topology 같은 것을 사용할때, ethernet 표준은 node들이 동시에 frame을 전송하면 충돌이 나는 broadcast link여서 이걸 처리하려고 CSMA/CD protocol을 사용한 것이다. 현재는 ethernet이 저장 후 전달 packet 교환을 하는 switch 기반의 star topology이다.

* unreliable connectionless service

adapter A가 datagram을 adapter B로 전송시 hand-shaking 없이 바로 frame으로 캡슐화 해서 보낸다. 또한 보내진 frame이 CRC 검사를 통화했는지 못했는지도 통보하지 않는다.

따라서, host의 application이 TCP인지 UDP인지에 따라 이것을 알아내거나 못알아낸다. TCP면 재전송하게 한다.
* link layer switch

* PPP(Point-to-Point Protocol)

* link virtualization - ATM, MPLS

1. ATM은 link layer의 기술로서 주로 사용되어 왔다. CBR(constant bit rate, 고정비트율), VBR(variable bit rate, 가용 비트율, ABR은 VBR하위의 것, 아직 읽어보지 않았지만 http://cntic03.hit.bme.hu/meres/ATMFAQ/d19.htm 요기에 대략적으로 나와있는 것 같음.) 이 존재한다. ATM은 packet switching 방식의 Virtual circuit network 구조이다.
   
   - ATM adaptation layer
   - ATM packet
   - ATM physical layer
   - IP over ATM
2. MPLS(Multiprotocol Label Switching, 다중 프로토콜 레이블 스위칭)
   VC network의 주요 개념은 고정 길이 레이블을 도입하여 IP router의 전달 속도를 향상시키려고 함.
   목표는 고정길이 레이블과 VC를 기반으로 하여 datagram을 전달하기 위해서 가능한 경우 datagram을 선택적으로 레이블링 한다.
   router로 하여금 목적지 IP address가 아닌 고정 길이 레이블을 기반으로 datagram을 전달할 수 있도록 하는 것이다. MPLS frame은 MPS 가능 routers 사이에서만 전송될 수 있다.
   종종 label-switched router라고 불리며, MPLS 가능 router는 destination IP address를 볼 필요도 없고, 최장프리픽스 대응을 할 필요도 없다.
   
                  
   R1, R2, R3, R4는 MPLS 가능 rotuer이고, R5, R6은 MPLS 불가능 router이다.
   R1이 자신을 통해 A로 packet을 보낼수 있음을 R2와 R3에게 알린다. 결국 R4역시 A로 갈수 있는 것을 알게된다. 이것을 table로 보일수 있는데 위와 같다.
   R4에서 선택된 packets들은 두개의 path로 전달 될수 있다.
   
   MPLS의 장점은 switching 속도를 향상시키며, traffic 관리가 가능핟. routing algorithm에 의해 나온 path는 한가지의 경우지만 MPLS의 경우 위의 예와 같이 2개의 path가 존재할수 있는 것이다.
   
   (MPLS 설명이 너무 부족하다..)