백투더코딩

빅오 표기법 사용

ex) O(N)

Big O

g(n)<=c*f(n):asymptotic upper bound

(c:some positive real constant N:some nonnegative integer s.t. for all n>=N)

g(n) is big O of f(n)

시간 복잡도를 계산할 때 상수는 버리며 가장 차수가 큰 변수를 기준으로 한다.

ex) n^2 와 n이 있을 경우 n^2이 빅오 표기법에 사용됨.

시간복잡도와 달리 공간 복잡도는 알고리즘 문제에서 크게 상관이 없는 경우가 많지만

필요없는 공간을 사용하고 있진않은지 신경을 쓸 필요는 있다.

B:Bytes b:bits

IP datagram(20-65535B ): Header(20-60B)+Data(<46B)

-Header format(20-60B)

Ver 4b

어떤 IP version

HLEN 4b

헤더의 길이

0-15로 *4를 해줘야 원래 값

Service type 8b

서비스 유형

패킷의 우선 순위 나타냄

Total length 16b

IP datagram 전체 길이

헤더길이도 포함

Identification 16b

Flags 3b

D: Do not fragment

M: More fragments

Fragmentation offset 13b

header 속 fragmentation

13bits라 3bits 부족하기 때문에 항상 /8

Time to live 8b

routing loop 방지

packet이 전파되는 범위 제한

Protocol 8b

프로토콜의 종류 ex) ICMP, IGMP, TCP, UDP, OSPF

Header checksum 16b

헤더만 오류탐지해주는 코드

Source IP address 4B

Destination 4B

Options+padding 0-40 B

single:byte multiple:type+length+value

type 8b+length 8b+value(variable)

type(1+2+5)

1:copy 2:class 5:number

single-byte:No operation, End of option

multiple-byte:Record route, Strict source route, Loose source route, Timestamp

MTU(Maximum Transfer Unit)

IP datagram 최대 길이

여러 논리 주소들을 하나의 주소로 합치는 것으로 subnet된 주소들을 다시 합친다고 생각하는 것과 같다.

슬래쉬를 활용해 netid의 갯수를 명확히 표시해줘야하며 address aggregation을 하면 

routing table의 크기가 줄어드는 장점이 있다.

netid를 hostid 방향으로 한 칸 옮길때마다 네트워크의 주소는 2배가 되고

hostid의 반대 방향으로 한 칸 옮길때마다 네트워크의 주소는 1/2배가 된다.

address aggregation의 예시는 아래와 같다. 

슬래쉬 뒤에 netid의 개수를 표현해 주었다.

라우팅 테이블을 보고 주소를 찾아갈때 address aggregation이 일어난 상황이라

여러 주소에 다 매칭이 된다면 longest mask matching으로 따라간다.  

Routing table을 활용해 패킷들이 알맞은 NextHopAdress를 찾아가며 경로를 찾아감

-Direct delivery

한 번 전달하고 나면 destination임

-Indirect delivery

여러 번 전달해야 destination임

Routing table

netmask는 netid부분을 다 1로 처리하고 hostid부분을 다 0으로 처리한 것인데 차후 다룰 예정

-오류 제어

Bit 오류: header의 오류탐지코드가 탐지

Lost: 응용계층에서 탐지

순서맞지않음:응용계층에서 탐지

중복:응용계층에서 탐지

-흐름 제어

응용계층에서 탐지

sender의 속도에 비해 receiver의 속도가 느리면 버퍼 오버플로우가 발생하며 packet loss가 발생

-혼잡 제어

network problem

너무 많은 sender packet이 존재하면 router의 버퍼에 오버플로우가 발생하며 packket loss 발생

송신자의 수:수신자의 수 

unicast 1:1

multicast 1:many

broadcast 1:all

anycast 1-to-any

calssful service에서는 각각의 통신서비스 별로 주소가 따로 존재함

나중에 다룰 예정!