게시 됨 업데이트 됨Lecture Summary / Computer Data Network

[강의정리] 데이터통신과네트워크 Link Layer

  • data-link layer: datagram을 서로 인접한 노드간에 전달해주는 책임을 가지고 있는 레이어

  • Links: 인접한 노드들을 따라서 communication channels를 연결

    • wired links
    • wireless links
    • LANs

  • Layer-2 packet: frame

    • Encapsulates datagram (데이타그램 캡슐화)

  • Framing: datagram을 frame로 만들고, header와 trailer를 붙임

  • Link access: share해서 사용할때 어떻게 나눠쓸건지 결정

    • “MAC” address in frame headers, source와 destination을 식별하는데 사용됨
      • IP address와 다름

  • 인접한 노드 사이에 신뢰성있는 데이터 전송

    • Wireless links: error가 많음
    • 드물게 low bit-error link 사용

  • Error detection: 신호 감소, 노이즈에 의한 에러 감지

  • Error correction: receiver는 retransmisson에 의존하지 않고 비트오류를 식별한후 수정함

  • Network interface 카드
  • Adaptors

Adaptors communicating

  • sending side: datagram 캡슐화, frameing

  • error checking bits, rdt등등 추가

  • receiving side: 에러, rdt등등 확인

  • 문제가 없으면 datagram를 추출해서 위로 보냄

Error detection

  • EDC = Error Detection and Correction bits

  • Error detection 100% 신뢰되진 않음

  • 하지만 거의 놓치지 않는다

  • EDC가 커질수록 detection과 correction이 쉬워짐

Parity checking

  • single bit parity: detect single bit errors

    • parity bit에 1의 개수가 짝수인지 홀수인지 확인

  • two-dimensional bit parity: detect and correct single bit errors

  • Row와 column에서 짝수 개수 확인, 에러 correction 가능

Checksum: 에러를 체크하는데 사용되는 함수 통칭

  • Sender send Msg with Checksum Value(CV)
  • Receiver check CV with Checksum

Checksumming Methods

  • Cyclic redundancy check (CRC)

    • error-detection coding으로 더 powerful

    • d bits(Data bits) + r bits(CRC bits)

    • CRC bits: D*2^r % G

  • 두가지 타입의 network links:
    • point-to-point link: single sender, single receiver
    • broadcast link (shared wire or medium): multiple sending and receiving

Multiple access protocols

  • single shared broadcast channel

  • 노드들에 의해서 동시에 데이터를 보낼 수 있어야함: interference

    • node가 동시에 signal을 보내려 하면 collision 발생

  • Multiple access protocol

    • node들이 channel을 share 하고 있을 때 어떤 노드가 먼저 보낼지 결정
    • 알고리즘은 모든 노드들에게 분산된 상태에서 구동되야함
    • Channel sharing에 관한 communication은 channel 자체를 사용해야함
      • 조정을 위해 out-of-band channel 사용하면 안됨

Multiple access protocol에 대한 이상적인 상황

  • Given: broadcast channel of rate R bps

  • 원하는 특성

    1. 하나의 노드가 데이터를 쓸 때, sending rate: R
    2. M개의 노드와 share할 때, send average rate: R/M
    3. Fully decentralized(완벽한 탈중앙화):
    • transmission을 조정하는 특별한 노트 X
    • 네트워크 시간동기화 가정 X
    1. simple

MAC (Media Access Control) protocols

  • Three broad classes:
    • channel partitioning
      • 채널을 작은 “조각”단위로 쪼개서 사용(time slots, frequency, code)
    • random access
      • 채널을 나누지 않고, 충돌이 일어나면 random한 delay로 대기
    • “taking turns”
    • 번갈아가면서 사용, 공평하지만 비효율적

Channel partitioning MAC protocols: TDMA

  • TDMA: time division multiple access
    • 시분할방식, 시간을 n-slot으로 나눠서 사용
    • 노는 slot이 생길 수 있으므로 비효율적

Channel partitioning MAC protocols: FDMA

  • FDMA: frequency division multiple access
    • 주파수 간격으로 데이터를 쪼갬

Random access protocols

  • node가 패킷을 보낼 때

    • 전체 채널 send rate R 사용
    • 노드간의 사전 조절은 X

  • 두개 이상의 노드가 동시에 사용하면 -> collision

  • Random access MAC protocol 특징:

    • 어떻게 충돌을 detect 할건지
    • 충돌이 일어났을 때 어떻게 recover 할 건지 (e.g., via delayed retransmissions)

  • Examples of random access MAC protocols:

    • slotted ALOHA
    • ALOHA
    • CSMA, CSMA/CD, CSMA/CA

Random Access protocols: Slotted ALOHA

  • 가정

    • all frames same size
    • 동등한 사이즈로 쪼갠 time divided slots
    • node가 slot 시작시간에 바로 transmit을 할 수 있음
    • 모든 노드들은 동기화 되있음
    • 2개 이상의 node가 하나의 slot에서 데이터를 보내려 하면, 모든 nodes가 충돌을 detect

  • 작업

    • 노드가 새로 보내야되는 frame이 있으면, 다음 slot에 transmits
      • if no collision: node는 새로운 frame을 다음 slot에 보낼 수 있음
      • if collision: node는 prob.p slot으로 retransmits, 성공할 때까지

  • Pros:

    • single active node라 transmit 을 full rate로 사용가능
    • simple

  • Cons

    • collisions, slot 낭비
    • 대기 슬롯
    • 시간 동기화

Random access protocols: CSMA

  • CSMA (carrier sense multiple access): transmit 하기 전 누가 사용하는지 확인

    • if channel sensed idle: transmit entire frame
    • if channel sensed busy, defer transmission

  • 대화하는데 끼어들지 않기

Random access protocols: CSMA collisions

  • Collision이 발생할 수 있음

    • propagation delay(전파 지연)

  • Collision

    • 패킷을 전부 보낼 때까지 시간 낭비됨

Random access protocols: CSMA/CD

  • CDMA/CD (collision detection)

    • 짧은 시간에 collisions detected
    • 충돌된 transmission 중단, channel wastage 감소

  • collsition detection:

    • easy in wired LANs: 신호 강도 측정, transmitted 비교, received signals
    • difficult in wireless LANs: 신호 왜곡이나 수신강도로 판단하기 어려움 (CSMA/CA 사용)

  • 예의 바른사람(끼어들어도 봐줌)

  • 구성

    1. NIC(Network Interface Card)가 datagram을 network layer로부터 받고 crates frame
    2. If NIC senses channel idle, frame transmission 시작, If NIC senses channel busy, channel이 idle 될때까지 대기후 tranmits.
    3. 만약 NIC가 다른 transmission의 방해 없이 transmit되면, 전송이 성공적으로 마무리됨
    4. 만약 NIC가 또다른 transmission detects하면, send를 abort(중단)함
    5. After aborting, NIC enter binary(exponential) backoff:
    • n-th의 collision이 발생하면, NIC는 {0, 1, 2, …, 2^n-1}중에 K를 랜덤하게 선택, NIC waits K*512 bits times, returns to Step 2
    • Longer backoff interval은 많은 collision이 있는것

Taking turns

Taking turns: polling protocol

  • master node에서 slave nodes에게 순서대로 transmit을 invites해줌

    • 일반적으로 “dumb”한 slave devices에서 사용

  • concerns(우려사항):

    • polling overhead
    • latency
    • single point of failure (master가 오류가 나면 전부 사용하지 못함)

Tacking turns: token passing

  • 토큰 메시지가 한 노드에서 다음 노드로 순서대로 전달됨

  • concerns(우려사항):

    • polling overhead
    • latency
    • single point of failure (token이 오류가 나면 전부 사용하지 못함)

Switched local networks

  • 3개 학과, 2개 서버와 4개의 스위치 라우터
  • 스위치들은 link-layer에서 동작
    1. link-layer frame으로 동작(L2 switch)
    2. network-layer address 인지못함
    3. routing algorithm 사용 못함(요즘은 됨)

MAC address and ARP

  • 32-bit ip address:

    • Network-layer 에서 사용하는 주소
    • layer 3에서 forwarding하는데 사용

  • MAC(or LAN or physical or Ethernet) address:

    • locally하게만 사용, 한 인터페이스마다 고유한 주소
    • 48 bit MAC address, NIC ROM에 고정되있음
    • e.g. 00:d0:ca:1c:f0:ed (3bytes: 제조업체 식별정보, 3bytes: 시리얼 넘버)

  • 데이터를 보낼 때 보내고자하는 Destination MAC 주소를 사용

  • Broadcast address (FF:FF:FF:FF:FF:FF)

MAC address (more)

  • MAC address는 IEEE에서 관리

  • 비유:

    • MAC address: 주민등록번호
    • IP address: 우편주소

  • MAC flat address -> 휴대성

    • LAN카드만 옮기면 됨

  • IP hierarchical address not protable

    • IP subnet때문에 휴대성 부족

ARP: address resolution protocol

  • 모든 PC들은 network-layer address(IP주소)와 link-layer address(MAC주소)를 같이 가지고 있음
    • 두 addresses 사이에 translate 필요
ARP table
  • 각 IP node들은 ARP table을 가지고 있음
  • ARP table 구성: <IP address, MAC address, TTL>
  • TTL(Time to Live): mapping이 유지되는 시간(일반적으로 20min)

ARP protocol: same LAN

  1. A는 Local에 있는 B에게 datagram을 전송하고 싶어함
  • A의 ARP table에는 B의 MAC address가 존재하지 않음
  1. A가 ARP query packet을 만들어서 B의 IP address를 포함한 후 broadcast해줌
  • Destination MAC address = FF-FF-FF-FF-FF-FF
  • All nodes on LAN receive ARP query
  1. B가 ARP packet 받음, A에게 자신의 MAC address 회신
  • A의 MAC address로 unicast
  1. A caches IP-to-MAC address를 pair로 ARP table에 저장
  • ARP is “plug-and-play”

Addressing: routing to another LAN

  • A에서 R을 거쳐 B로 datagram send
  1. create IP datagram with IP source A, destination B
    link-layer frame의 destination address를 R의 MAC address로 전송
  2. frame sent from A to R
    R에서 frame 수신, datagram removed, passed up to IP
  3. R에서 IP source A, destination B로 datagram forward
    link-layer frame의 destination address는 B의 MAC address, source는 R
    회신도 같은 구조

Ethernet

  • wired Lan technology의 표준:

    • 먼저 널리 사용된 LAN technology
    • 간단하고, 저렴함
    • 성능도 좋음

  • bus: 90년도까지 사용

    • 모든 노드는 same colision domain (서로 충돌할 수 있음)

  • star: 오늘날 사용

    • 중앙에 스위치 활성화
    • 각각 direct로 사용

Ethernet frame structure

  • Sending adapter는 Ethernet frame에 IP datagram을 캡슐화

  • Preamble (8bytes)

    • 정해져있는 패턴
    • 시작점을 포착하기 위함, 동기화용

  • Addresses (6bytes)

    • source, destination MAC address

  • Type (2bytes)

    • higher layer protocol을 나타냄 (주로 IP)

  • Data field (46 to 1,500 bytes)

    • IP datagram 포함
    • 이더넷의 MTU(Maximum transmission unit)이 1,500 bytes로 정해짐

  • CRC (4bytes)

    • Error detected

Ethernet: unreliable, conntectionless

  • Connectionless (연결없음)

    • no handshaking betwween sending and receiving NICs

  • Unreliable (신뢰하지 않는)

    • NIC는 acks랑 nacks를 보내지 않음

  • initial sender가 higher layer rdt(e.g., TCP)를 사용하는 경우에만 dropped된 frames를 recovered해주고, 그외에는 데이터를 버림

  • Ethernet’s MAC protocol

    • unslotted CSMA/CD with binary backoff

  • Link-layer device: takes an active role

    • switch의 역할: 받은 패킷을 다른쪽 links로 forawrd 해주는 역할

  • transparent(투명함)

    • host는 switches의 존재를 알아차리기 어려움
    • forwarding만 해주기 때문

  • plug-and-play, self-learning

Filtering과 forwarding

  • Filtering: Switch function이 하는 역할, frame을 어디로 보내야할지, drop시켜야할지 결정
  • Forwarding: Filtering에서 보내져야할 패킷이라고 결정되면, Input port에 따라서 어느 output port로 보내야할지 결정

Switch: multiple simultaneous transmissons

  • 각 호스트는 switch와 개별로 연결되있음
  • 동시에 들어와도 collision이 발생하지 않음

Switch: self-learning

  • 스위치는 어떤 인터페이스를 통해 어떤 호스트로 갈 수 있는지 학습

    • frame을 가져오면, 스위치는 sender의 주소를 “학습”: 들어오는 LAN segment

    • sender/location pair 을 switch table에 기록

    • frame destination을 모르면, broadcast

    • reply 받으면 기록

Switches vs. Routers

  • 둘 다 store and forward:

    • routers: network-layer devices
    • switches: link-layer devices

  • 둘 다 forwarding table 존재:

    • routers: IP주소 기반
    • switches: MAC 주소 기반

  • 하지만 최근엔 L3 switches 사용

VLAN (Virtual Local Area Network)

  • single broadcast domain:

    • all layer-2 broadcast traffic
    • security/privacy, efficiency issues

  • Virtual Local Area Network: broadcast domain을 나누어주는 역할

  • 1개의 switch를 가상으로 2개의 switch가 있다고 생각할 수 있도록 만들어줌

  • 라우터를 이용하여 VLAN끼리 통신

  • trunk port: 여러개의 물리적인 스위치에 정의된 VLAN간에 프레임 전달

Summary: A day in the life of a web request

  1. DHCP로 IP주소를 받아옴
  2. ARP로 DNS서버 접근, 주소를 받아옴
  3. TCP connection(3-way handshaking)
  4. HTTP request를 보냄, reply 받음
  5. 웹페이지 열림
#

댓글

카테고리

태그

Algorithm15
Computer Math3
Computer Network11
Div.21
Div.31
Information Science1
Problem Solve5
summary2
×