Ochrona informacji w sieciach komputerowych PDF

Ochrona informacji w sieciach komputerowych Plan całości wykładu 1. Wprowadzenie (2 wykłady) (2 wykłady) Warstwa transportu (2 wykłady) Warstwa sieci (3 wykłady) Warstwa łącza i sieci lokalne (3 wykłady) Podstawy ochrony informacji (3 wykłady) Cele wykładu: 1. zrozumienie zasad ochrony informacj...

Ochrona informacji w sieciach komputerowych Plan całości wykładu 1. Wprowadzenie (2 wykłady) (2 wykłady) Warstwa transportu (2 wykłady) Warstwa sieci (3 wykłady) Warstwa łącza i sieci lokalne (3 wykłady) Podstawy ochrony informacji (3 wykłady) Cele wykładu: 1. zrozumienie zasad ochrony informacji: 2. Warstwa aplikacji 3. 4. 5. 6. kryptografia i jej wiele zastosowań poza “poufnością”  uwierzytelnienie  integralność  dystrybucja kluczy  2. ochrona informacji w praktyce:  ściany ogniowe i systemy wykrywania włamań  ochrona informacji w warstwach aplikacji, transportu, sieci, łącza, i fizycznej Ochrona informacji 1 Ochrona informacji 2 Co to jest ochrona informacji? Mapa wykładu 7.1 Co to jest ochrona informacji? 7.2 Zasady działania kryptografii 7.3 Uwierzytelnienie 7.4 Integralność 7.5 Dystrybucja kluczy i certyfikacja 7.6 Kontrola dostępu: ściany ogniowe 7.7 Ataki i środki zaradcze 7.8 Wykrywanie włamań i cyfrowa kryminalistyka 7.9 Ochrona informacji w wielu warstwach Ochrona informacji 3 Ochrona informacji Co to jest ochrona informacji? Co to jest ochrona informacji? Poufność: tylko nadawca, zamierzony odbiorca powinien “rozumieć” zawartość wiadomości  nadawca szyfruje wiadomość  odbiorca odszyfrowuje wiadomość Poufność: tylko nadawca, zamierzony odbiorca powinien “rozumieć” zawartość wiadomości  nadawca szyfruje wiadomość  odbiorca odszyfrowuje wiadomość Uwierzytelnienie: nadawca, odbiorca chcą wzajemnie potwierdzić swoją tożsamość Ochrona informacji 5 Ochrona informacji 4 6 1 Co to jest ochrona informacji? Co to jest ochrona informacji? Poufność: tylko nadawca, zamierzony odbiorca powinien “rozumieć” zawartość wiadomości  nadawca szyfruje wiadomość  odbiorca odszyfrowuje wiadomość Uwierzytelnienie: nadawca, odbiorca chcą wzajemnie potwierdzić swoją tożsamość Integralność: nadawca, odbiorca chcą zapewnić, że wiadomość nie zostanie zmodyfikowana (podczas komunikacji, lub później) niepostrzeżenie Poufność: tylko nadawca, zamierzony odbiorca powinien “rozumieć” zawartość wiadomości  nadawca szyfruje wiadomość  odbiorca odszyfrowuje wiadomość Uwierzytelnienie: nadawca, odbiorca chcą wzajemnie potwierdzić swoją tożsamość Integralność: nadawca, odbiorca chcą zapewnić, że wiadomość nie zostanie zmodyfikowana (podczas komunikacji, lub później) niepostrzeżenie Dostępność: usługi muszą być dostępne dla użytkowników Ochrona informacji 7 Przyjaciele i wrogowie: Alicja, Bob, Trudy  Bob, Alicja (dobrzy znajomi) chcą porozumiewać się  … najprościej, prawdziwymi ludźmi! “bezpiecznie”  Trudy (intruz) może przechwytywać, usuwać, dodawać komunikaty kanał bezpieczny nadawca dane  Przeglądarka/serwer WWW dla Bob dane, komunikaty sterujące bezpieczny odbiorca 8 Kim mogą być Bob i Alicja?  dobrze znani w środowisku ochrony informacji Alicja Ochrona informacji dane elektronicznych transakcji (n.p., zakupy on-line)  klient/serwer banku on-line  serwery DNS  rutery wymieniające aktualizacje tablic rutingu  inne przykłady? Trudy Ochrona informacji 9 Na świecie są źli ludzie... Ochrona informacji 10 Na świecie są źli ludzie... Co może zrobić “zły człowiek”? Odpowiedź: bardzo dużo! Czy można się zabezpieczyć technologicznie? Odpowiedź: nie można!  podsłuchiwać: przechwytując wiadomości  aktywnie dodawać wiadomości do komunikacji  podszywać się: może fałszować (spoof) adres    karteczki z hasłami  "pożyczanie" konta  logowanie się na obcym komputerze nadawcy w pakiecie (lub dowolne pole w pakiecie)  przechwytywać: “przejmować” istniejące połączenie przez usunięcie nadawcy lub odbiorcy, zastępując go sobą, przejmować kontrolę nad hostem nadawcy/odbiorcy  zablokować usługę: uniemożliwić dostęp do usługi innym (ang. denial of service) Ochrona informacji ataki technologiczne i środki zaradcze to przedmiot tego wykładu, lecz......najprostszy atak, to wykorzystanie słabości człowieka! ...a najskuteczniejszy atak, to połączenie socjotechniki z atakiem technologicznym...  np., nakłonienie ofiary do zainstalowania konia trojańskiego.. Bądźcie ciągle czujni!! (Mad-Eyed Moody) 11 Ochrona informacji 12 2 Mapa wykładu Krypto... –grafia, -analiza i NSA 7.1 Co to jest ochrona informacji? 7.2 Zasady działania kryptografii 7.3 Uwierzytelnienie 7.4 Integralność 7.5 Dystrybucja kluczy i certyfikacja 7.6 Kontrola dostępu: ściany ogniowe 7.7 Ataki i środki zaradcze 7.8 Wykrywanie włamań i cyfrowa kryminalistyka 7.9 Ochrona informacji w wielu warstwach  Kryptologia: jak zabezpieczyć informację przed niepowołanym dostępem Niemiecka maszyna szyfrująca Lorenza,  Od początku, konkurują ze sobą dwie dziedziny wiedzy:   Ochrona informacji 13 Krypto... –grafia, -analiza i NSA   służba?  Palladium (& TCPA): globalne tylne drzwi?  zapewne będzie częścią MS Longhorn  obecna oficjalna nazwa: Next-Generation Secure Computing Base for Windows, „Trusted Computing”  tak naprawdę chodzi o... DRM (Digital Rights Management) czyli o zarządzanie prawem dostępu do informacji cyfrowej Kryptografia – utajnianie wiadomości Kryptoanaliza - odwrotnie Steganografia – rodzaj szyfrowania polgający na ukryciu samego przekazu Steganaliza - idwritnbie Ochrona informacji 15 Klucz Alicji otwarty tekst algorytm szyfrujący wiadomość zaszyfrowana Ochrona informacji 16 Kryptografia z kluczem symetrycznym Język kryptografii K szyfrujący A 14  NSA (National Security Agency): globalna tajna dziedziny wiedzy:  Ochrona informacji Krypto... –grafia, -analiza i NSA  Od początku, konkurują ze sobą dwie   Kryptografia kryptoanaliza nowe dziedziny: steganografia, steganaliza szyfr zastępujący: zastępuje niektóre części przez inne Klucz K odszyfrowujący  B Boba algorytm otwarty tekst odszyfrowujący szyfr monoalfabetyczny: zastępuje jeden znak przez inny otwarty tekst: abcdefghijklmnopqrstuvwxyz zaszyfrowany tekst: mnbvcxzasdfghjklpoiuytrewq N.p.: otwarty t.: Kocham cię, Bob. Alicja zaszyfrowany t.: nkn. s gktc wky. mgsbc kryptografia z kluczem symetrycznym: klucze nadawcy, odbiorcy są identyczne kryptografia z kluczem publicznym: jeden klucz publiczny, drugi klucz tajny (prywatny) Ochrona informacji Pytanie: Jak trudno jest złamać ten prosty szyfr?:  brutalnie (jak trudno?)  w inny sposób? 17 Ochrona informacji 18 3 Kryptografia z kluczem symetrycznym  Czy istnieje szyfr nie do złamania? KA-B KA-B algorytm otwarta wiadomość, m szyfrujący Idealnie bezpieczny szyfr zaszyfrowana wiadomość K (m) A-B algorytm otwarty tekst odszyfrom=K ( K (m) ) wujący A-B A-B kryptografia z kluczem symetrycznym: Bob i Alicja znają ten sam (symetryczny) klucz: KA-B  n.p., kluczem może być wzorzec zastępowania w monoalfabetycznym szyfrze zastępującym  Pytanie: jak Bob i Alicja mają uzgodnić wartość klucza? Ochrona informacji 19 Ochrona informacji Idealnie bezpieczny szyfr Idealnie bezpieczny szyfr  Czy istnieje szyfr nie do złamania?  Czy istnieje szyfr nie do złamania?  Odpowiedź: tak!  Odpowiedź: tak! 20 wystarczy zaszyfrować wiadomość za pomocą klucza, który jest losowym ciągiem bitów tak samo długim jak wiadomość algorytm szyfrujący: m XOR k niestety: to nie jest praktyczne rozwiązanie... Kryptografia: sztuka znajdowania szyfrów, które wykorzystują krótkie klucze i nie dają się łatwo złamać Ochrona informacji 21 Kryptografia symetryczna: DES DES: Data Encryption Standard 1. Amerykański standard szyfrowania [NIST 1993] 2. 56-bitowy klucz symetryczny, otwarty tekst w blokach 64-bitowych 3. Jak bezpieczny jest DES?  DES Challenge: wiadomość zaszyfrowana 56bitowym kluczem (“Strong cryptography makes the world a safer place”) została odszyfrowana (za pomocą brutalnej siły) w 4 miesiące  nie są znane “tylne drzwi” do odszyfrowywania 4. zwiększanie bezpieczeństwa DES:  używanie 3 kluczy po kolei (3-DES)  łączenie bloków szyfru Ochrona informacji 23 Ochrona informacji 22 Ochrona informacji 24 Kryptografia symetryczna: DES Działanie DES początkowa permutacja 16 identycznych “rund”, każda używa innych 48 bitów klucza końcowa permutacja 4 Kryptografia symetryczna: DES EFF DES cracker (nazywany też Deep Crack) – urządzenie zbudowane przez Electronic Frontier Foundation (EFF) w 1998 roku do łamania szyfrów DES metodą siłową, czyli przez sprawdzenie wszystkich możliwych kluczy. Zostało zbudowane w celu pokazania, że szyfr DES nie może być uważany za bezpieczny. AES: Advanced Encryption Standard  nowy (Listopad 2001) standard NIST kryptografii symetrycznej, zastępujący DES  przetwarza dane w 128-bitowych blokach  128, 192, lub 256 bitowe klucze  brutalne odszyfrowanie (wypróbowanie każdego klucza) dla wiadomości i długości klucza, które trwa 1 sekundę dla DES, trwa 149 bilionów lat dla AES Jeden z obwodów drukowanych urządzenia DES cracker, Na zdjęciu pokazane są 32 z 1856 dedykowanych procesorów. 5a-25 kryptografia klucza publicznego  radykalnie inne podejście [DiffieHellman 1976, RSA 1978]  nadawca, odbiorca nie mają wspólnego klucza  publiczny klucz nadawcy/odbiorcy jest znany wszystkim  prywatny klucz jest znany tylko właścicielowi Ochrona informacji + Klucz publiczny B Boba K K algorytm otwarta wiadomość, m szyfrujący zaszyfrowana wiadomość + K (m) B 27 - Klucz prywatny B Boba algorytm otwarta odszyfro- wiadomość + wujący m = K (K (m)) B RSA: Wybór kluczy Wymagania: 1. Wybierz dwie duże liczby pierwsze p, q. (n.p., po 1024 bity każda). B B -. 1 potrzeba KB ( ) i KB ( ) takich, że - + K (K (m)) = m 28 2. Oblicz n = pq, z = (p-1)(q-1) 3. Wybierz e (przy tym e1) co z. (e, z są “względnie pierwsze”). + 2 znając klucz publiczny KB , obliczenie klucza prywatnego KB powinno być niemożliwe 4. Wybierz d takie, że ed-1 jest podzielne przez z. (innymi słowy: ed mod z = 1 ). 5. Klucz publiczny to (n,e). Klucz prywatny to (n,d). RSA: algorytm Rivest, Shamir, Adleman Ochrona informacji B Ochrona informacji Algorytmy szyfrujące z kluczem publicznym + 26 Kryptografia klucza publicznego Kryptografia z kluczem publicznym kryptografia symetryczna  nadawca i odbiorca muszą znać wspólny, tajny klucz symetryczny  Pytanie: jak uzgodnić wartość klucza (szczególnie, jeśli nadawca i odbiorca nigdy się nie “spotkali”)? Ochrona informacji + KB 29 - KB Ochrona informacji 30 5 RSA: Szyfrowanie, odszyfrowywanie Przykład RSA: Bob wybiera p=5, q=7. Then n=35, z=24. e=5 (tak że e, z względnie pierwsze). d=29 (tak że ed-1 podzielne przez z. 0. Mając (n,e) oraz (n,d) obliczone jak powyżej 1. Żeby zaszyfrować ciąg bitów, m, oblicz e c = m e mod n (resztę z dzielenie m przez n) 2. Żeby odszyfrować ciąg bitów, c, oblicz szyfrowanie: d m = c d mod n (resztę z dzielenia c przez n) odszyfrowywanie: Czary m = (m e mod n) d mod n z mleka! c Ochrona informacji testy na liczby pierwsze pierwsze z z? 3.  c = me mod n l 12 1524832 17 d c c 17 481968572106750915091411825223071697 Ochrona informacji Jak obliczyć d z e? = m zmodyfikowany algorytm Euklidesa ed mod (p-1)(q-1) mod n (używając wyniku opisanego powyżej) 1 = m mod n potęgi? (ponieważ wybraliśmy ed podzielne przez (p-1)(q-1) z resztą 1 ) arytmetyka dowolnej precyzji Ochrona informacji Ochrona informacji 34 RSA: inna ważna własność Przecież w kluczu publicznym znane jest n=pq? Czy nie da się z niego poznać p,q? 2. Odpowiedź: nie tak łatwo... 1. Następująca własność będzie bardzo ważna później: B + B + B B K (K (m)) = m = K (K (m)) problem poznania wszystkich liczb pierwszych, których iloczyn równy jest danej liczbie, to użyj najpierw klucza publicznego, potem prywatnego faktoryzacja Faktoryzacja jest problemem NP-trudnym (bardzo złożonym obliczeniowo)  Odpowiedź: da się złamać RSA, ale trwa to bardzo długo...  jeśli P=NP, to może kryptografia klucza publicznego przestanie być skuteczna Ochrona informacji = m 33 Dlaczego RSA trudno odszyfrować?  32 e (m mod n) d mod n = medmod n algorytm Euklidesa 4. Jak podnieść liczbę do bardzo dużej  m = cd mod n litera 12 l Pożyteczny wynik z teorii liczb: Jeśli p,q są liczbami pierwszymi i n = pq, to: y y mod (p-1)(q-1) x mod n = x mod n 2. Jak sprawdzić, że e jest względnie  me RSA: Dlaczego m = (m e mod n) d mod n Szukanie dużych liczb pierwszych  m 31 Praktyczne problemy przy implementacji RSA 1. litera użyj najpierw klucza prywatnego, potem publicznego Wynik jest ten sam! 35 Ochrona informacji 36 6 Uwierzytelnienie Mapa wykładu 7.1 Co to jest ochrona informacji? 7.2 Zasady działania kryptografii 7.3 Uwierzytelnienie 7.4 Integralność 7.5 Dystrybucja kluczy i certyfikacja 7.6 Kontrola dostępu: ściany ogniowe 7.7 Ataki i środki zaradcze 7.8 Wykrywanie włamań i cyfrowa kryminalistyka 7.9 Ochrona informacji w wielu warstwach Ochrona informacji Cel: Bob chce, żeby Alicja “udowodniła” jemu swoją tożsamość Protokół uwierz1.0: Alicja mówi: “Jestem Alicja”. “Jestem Alicja” 37 Uwierzytelnienie Scenariusz błędny?? Ochrona informacji 38 Uwierzytelnienie: druga próba Protokół uwierz2.0: Alicja mówi “Jestem Alicja” w pakiecie IP, który zawiera jej adres IP Cel: Bob chce, żeby Alicja “udowodniła” jemu swoją tożsamość Protokół uwierz1.0: Alicja mówi: “Jestem Alicja”. “Jestem Alicja” w sieci, Bob nie “widzi” Alicji, zatem Trudy po prostu oświadcza, że jest Alicją Ochrona informacji Adres IP “Jestem Alicja” Alicji Scenariusz błędny?? 39 Ochrona informacji Uwierzytelnienie: kolejna próba Uwierzytelnienie: druga próba Protokół uwierz2.0: Alicja mówi “Jestem Alicja” w pakiecie IP, który zawiera jej adres IP Protokół uwierz3.0: Alicja mówi “Jestem Alicja” i wysyła swoje tajne hasło, żeby “udowodnić” tożsamość. Adres IP Alicji Trudy może stworzyć pakiet, w którym podaje Adres IP “Jestem Alicja” adres IP Alicji Alicji jako adres źródła (IP spoofing”) Ochrona informacji 40 41 Hasło Alicji “Jestem Alicja” Adres IP OK Alicji Scenariusz błędny?? Ochrona informacji 42 7 Uwierzytelnienie: jeszcze jedna próba Uwierzytelnienie: kolejna próba Protokół uwierz3.0: Alicja mówi “Jestem Alicja” i wysyła swoje tajne hasło, żeby “udowodnić” tożsamość. Adres IP Alicji Hasło Alicji “Jestem Alicja” Protokół uwierz3.1: Alicja mówi “Jestem Alicja” i wysyła swoje zaszyfrowane tajne hasło, żeby “udowodnić” tożsamość. Atak odtwarzający: Trudy nagrywa pakiet Alicji i później odtwarza go dla Boba Adres IP OK Alicji Hasło Alicji Adres IP Alicji Scenariusz błędny?? Adres IP OK Alicji “Jestem Alicja” Ochrona informacji 43 Uwierzytelnienie: jeszcze jedna próba Adres IP Zaszyfro- “Jestem Alicji wane hasło Alicja” Uwierzytelnienie: ponowna próba uwierz4.0: żeby sprawdzić, czy Alicja "żyje", Bob wysyła jej id. jednorazowy, R. Alicja musi odesłać R, zaszyfrowane wspólnym kluczem symetrycznym “Jestem Alicja” R KA-B(R) Adres IP Zaszyfro- “Jestem Alicji wane hasło Alicja” Błędy, wady? Ochrona informacji 45 Uwierzytelnienie: uwierz5.0 + - K A (R) “wyślij mi swój klucz publiczny” + KA Ochrona informacji 46 Atak pośrednika (ang. man in the middle): Trudy udaje Alicję (dla Boba) i Boba (dla Alicji) Jestem Alicja R Bob oblicza - KA(KA (R)) = R i wie, że tylko Alicja może znać klucz prywatny, który zaszyfrował R tak, że + K (K (R)) = R A A Ochrona informacji Alicja "żyje", i tylko Alicja zna klucz, zatem to musi być Alicja! uwierz5.0: luka w bezpieczeństwie uwierz4.0 wymaga wspólnego klucza symetrycznego r czy możemy uwierzytelniać za pomocą kryptografii klucza publicznego? uwierz5.0: używa id. jednorazowego, kryptografii klucza publicznego “Jestem Alicja” 44 Identyfikator jednorazowy: liczba (R) używana raz w życiu nagrywanie i odtwarzanie ciągle działa! Adres IP OK Alicji Ochrona informacji Cel: uniknąć ataku odtwarzającego Protokół uwierz3.1: Alicja mówi “Jestem Alicja” i wysyła swoje zaszyfrowane tajne hasło, żeby “udowodnić” tożsamość. R Adres IP Zaszyfro- “Jestem Alicji wane hasło Alicja” 47 K (R) A Jestem Alicja R K (R) T Wyślij mi swój klucz publiczny K Wyślij mi swój klucz publiczny + K A - + m = K (K (m)) A A + K (m) A + T + K (m) T Trudy poznaje - + m = K (K (m)) T T wysyła m do Alicji, zaszyfrowane kluczem publicznym Alicji Ochrona informacji 48 8 "Atak na RSA" Mapa wykładu Atak pośrednika (ang. man in the middle): Trudy udaje Alicję (dla Boba) i Boba (dla Alicji) r 7.1 Co to jest ochrona informacji? r 7.2 Zasady działania kryptografii Trudny do rozpoznania:  Bob otrzymuje wszystko, co Alicja wysłała, i na odwrót. (dzięki temu Bob, Alicja mogą się spotkać później i wiedzą, o czym rozmawiali)  rzecz w tym, że Trudy też zna wszystkie wiadomości!  Problem polega na tym, że Bob "poznał" klucz publiczny Alicji w niebezpieczny sposób  Problem dotyczy wszystkich zastosowań kryptografii z kluczem publicznym Ochrona informacji r 7.3 Uwierzytelnienie r 7.4 Integralność r 7.5 Dystrybucja kluczy i certyfikacja r 7.6 Kontrola dostępu: ściany ogniowe r 7.7 Ataki i środki zaradcze r 7.8 Wykrywanie włamań i cyfrowa kryminalistyka r 7.9 Ochrona informacji w wielu warstwach 49 Mapa wykładu Ochrona informacji Podpisy cyfrowe 7.1 Co to jest ochrona informacji? 7.2 Zasady działania kryptografii 7.3 Uwierzytelnienie 7.4 Integralność 7.5 Dystrybucja kluczy i certyfikacja 7.6 Kontrola dostępu: ściany ogniowe 7.7 Ataki i środki zaradcze 7.8 Wykrywanie włamań i cyfrowa kryminalistyka 7.9 Ochrona informacji w wielu warstwach Ochrona informacji Technika kryptograficzna analogiczna do podpisów odręcznych. 1. fałszerstwem: odbiorca (Alicja) może udowodnić komuś, że Bob, i nikt inny (również sama Alicja), podpisał dokument 51 Bob podpisuje m przez zaszyfrowanie wiadomości z pomocą swojego klucza prywatnego KB, tworząc “podpisaną” wiadomość, KB(m) Kochana Alicjo O, jak strasznie tęsknię. Myślę o Tobie przez cały czas! …(bla bla bla) Bob Ochrona informacji 52 Podpisy cyfrowe (cd) Prosty podpis cyfrowy dla wiadomości m: Wiadomość Boba, m nadawca (Bob) podpisuje dokument cyfrowo, twierdząc że jest właścicielem/twórcą dokumentu. 2. weryfikacja, zabezpieczenie przed Podpisy cyfrowe 1. 50 - K B Klucz prywatny Boba Algorytm szyfrowania z kluczem publicznym K B(m) Załóżmy, że Alicja otrzymuje wiadomość m, podpis cyfrowy KB(m) 2. Alicja sprawdza m podpisaną przez Boba przez użycie klucza + + publicznego Boba KB do KB(m) i sprawdzenie, czy KB(KB(m) ) = m. 3. Jeśli KB(KB(m) ) = m, to osoba, która podpisywała m, musiała użyć klucza prywatnego Boba. + - Alicja sprawdza, że: Bob podpisał m. Nikt inny nie podpisał m. Bob podpisał m, a nie m’. Niezaprzeczalność: Alicja może wziąć m, oraz podpis KB(m) do sądu i udowodnić, że Bob podpisał m. Wiadomość Boba, m, podpisana (zaszyfrowana) jego kluczem prywantym Ochrona informacji 1. 53 Ochrona informacji 54 9 Skróty wiadomości Szyfrowanie długich wiadomości w kryptografii klucza publicznego jest drogie obliczeniowo Cel: prostu do obliczenia, cyfrowy skrót wiadomości 1. zastosuj funkcję haszującą H do m, uzyskując skrót wiadomości o ustalonej długości, H(m). duża wiadomość m Internetowa suma kontrolna: słaba funkcja haszująca H: Funkcja haszująca H(m) Własności funkcji haszujących: 1. nie są różnowartościowe 2. tworzą skróty ustalonej długości 3. mając dany skrót x, znalezienie m takiego, że x = H(m), jest bardzo trudne obliczeniowo Ochrona informacji duża wiadomość m Alicja sprawdza podpis o integralność podpisanej wiadomości: Funkcja haszująca H klucz prywatny Boba + - KB podpis cyfrowy (szyfruj) zaszyfrowany skrót KB(H(m)) duża wiadomość klucz m wiadomość format ASCII wiadomość format ASCII I O U 1 0 0. 9 9 B O B 49 4F 55 31 30 30 2E 39 39 42 D2 42 I O U 9 0 0. 1 9 B O B 49 4F 55 39 30 30 2E 31 39 42 D2 42 B2 C1 D2 AC różne wiadomości lecz identyczne skróty! B2 C1 D2 AC Ochrona informacji 56 Algorytmy funkcji haszujących Szeroko używana funkcja MD5 (RFC 1321) oblicza 128-bitowy skrót wiadomości w czterostopniowym procesie. mając dowolny 128-bitowy ciąg x, trudno jest skonstruować wiadomość m której hasz MD5 jest równy x. 2. SHA-1 także jest używany. Standard amerykański [NIST, FIPS PUB 180-1] skrót 160-bitowy 1. zaszyfrowany skrót H(m) Jednak znając wiadomość i jej skrót, łatwo jest znaleźć inną wiadomość o tym samym skrócie: 55 Podpis cyfrowy = podpisany skrót wiadomości Bob wysyła wiadomość podpisaną cyfrowo: Internetowa suma kontrolna ma niektóre własności funkcji haszującej: 1. tworzy skróty ustalonej długości (16-bitowe) 2. nie jest różnowartościowa KB(H(m)) podpis publiczny cyfrowy + Funkcja Boba K B (odszyfruj) haszująca H H(m) H(m) równe ? Ochrona informacji 57 Ochrona informacji 58 Bezpieczna poczta Mapa wykładu  Alicja chce wysłać poufny list, m, do Boba. 7.1 Co to jest ochrona informacji? 7.2 Zasady działania kryptografii 7.3 Uwierzytelnienie 7.4 Integralność 7.5 Dystrybucja kluczy i certyfikacja 7.6 Kontrola dostępu: ściany ogniowe 7.7 Ataki i środki zaradcze 7.8 Wykrywanie włamań i cyfrowa kryminalistyka KS m S + KS 7.9 Ochrona informacji w wielu warstwach Ochrona informacji +. KB( ) + K 7.8.1. Bezpieczna poczta 7.8.2. Bezpieczne gniazda 7.8.3. IPsec 7.8.4. 802.11 WEP 7.8.5. TEMPEST i poufność w warstwie fizycznej KS(m ). K (m ) KS( ) B + KB(KS ). KS( ) - Internet KS -. KB( ) + KB(KS ) m K B Alicja: 59  generuje losowy symetryczny klucz prywatny, KS.  szyfruje wiadomość kluczem KS (dla wydajności)  szyfruje także KS kluczem publicznym Boba.  wysyła zarówno KS(m) jak i KB(KS) do Boba. Ochrona informacji 60 10 Bezpieczna poczta Bezpieczna poczta (cd)  Alicja chce wysłać poufny list, m, do Boba. Alicja chce zapewnić integralność listu i uwierzytelnić się Bobowi. KS. m KS( ) KS(m ) KS(m ) + + KS. KB( ) - Internet + + KB(KS ) KB(KS ) + K. KS( ) KA m KS -. -. K- (H(m)) A + 1. 2. KS. KS( ) + m KS m. H(m ) porównaj. H( ) H(m ) Ochrona informacji - KA( ) - + KA( ) 62 Pretty good privacy (PGP) integralność listu.. Internet 61 Alicja chce zapewnić poufność, uwierzytelnienie nadawcy, H( ) A wysyła list (otwartym tekstem) i podpis cyfrowy. Bezpieczna poczta (cd) m. K (H(m)) KA( ) KA Alicja podpisuje list cyfrowo.  używa swojego prywatnego klucza do odszyfrowania KS  używa KS do odszyfrowania KS(m) i odzyskania m KA - KA(H(m)) m Bob: Ochrona informacji. H( ) - - + KB( ) K B B + - m +. KB( ) + Internet 3. + KB(KS ) KB 4. Alicja używa trzech kluczy: swojego prywatnego, publicznego Boba, nowego klucza symetrycznego Ochrona informacji 63 Mechanizm szyfrowania poczty elektronicznej, standard de-facto. używa kryptografii symetrycznej, kryptografii z kluczem publicznym, funkcji haszujących, i podpisów cyfrowych. zapewnia poufność, uwierzytelnienie nadawcy, integralność. wynalazca, Phil Zimmerman, był obiektem śledztwa w USA przez 3 lata. Wiadomość podpisana przez PGP: ---BEGIN PGP SIGNED MESSAGE--Hash: SHA1 Kochany Bobie: Mój mąż wyjechał dziś w delegację. Ubóstwiam Cię, Alicja ---BEGIN PGP SIGNATURE--Version: PGP 5.0 Charset: noconv yhHJRHhGJGhgg/12EpJ+lo8gE4vB3mqJ hFEvZP9t6n7G6m5Gw2 ---END PGP SIGNATURE--- Ochrona informacji 64 Plan całości wykładu 1. 2. 3. 4. 5. 6. Wprowadzenie (2 wykłady) Warstwa aplikacji (2 wykłady) Warstwa transportu (3 wykłady) Warstwa sieci (3 wykłady) Warstwa łącza i sieci lokalne (2 wykłady) Podstawy ochrony informacji (3 wykłady) KONIEC Ochrona informacji 65 11 Plan całości wykładu Mapa wykładu r Wprowadzenie r Warstwa aplikacji r Warstwa transportu r Warstwa sieci r Warstwa łącza i sieci lokalne r Podstawy ochrony informacji (2 wykłady) (2 wykłady) (2-3 wykłady) (2-3 wykłady) (3 wykłady) (2-3 wykłady) 5.1 Wprowadzenie i usługi warstwy łącza 5.2 Rozpoznawanie i naprawa błędów 5.3 Protokoły wielodostępowe 5.4 Adresy w sieciach LAN oraz protokół ARP 5.5 Ethernet r r r r r r r r r r 5.6 Koncentratory, mosty, i switche 5.7 Bezprzewodowe łącza i sieci lokalne 5.8 PPP 5.9 ATM 5.10 Frame Relay 5a-1 Łącza współdzielone i protokoły wielodostępowe 5a-2 Protokoły wielodostępowe Dwa rodzaje “łącz”: r punkt-punkt r r punkt-wielopunkt, rozgłaszające (wspólny kabel lub medium) protokół wielodostępowy m łącze punkt-punkt pomiędzy switchem Ethernet i hostem r wspólne łącze rozgłaszające dwie lub więcej jednoczesnych transmisji: zakłócenia m PPP dla dostępu modemowego m tylko jeden węzeł może poprawnie nadawać w chwili czasu rozproszony algorytm, który określa jak węzły dzielą się łączem, czyli jak węzeł określa, kiedy może nadawać r komunikacja sygnalizacyjna o podziale łącza musi sama używać tego łącza! r czego wymagać od protokołów wielodostępowych: r m tradycyjny Ethernet m HFC (hybrid fibre - coaxial ) - światłowód m bezprzewodowa sieć lokalna 802.11 wspólny kabel (n.p. Ethernet) wspólne radio (n.p. Bluetooth) satelita impreza 5a-3 5a-4 Protokoły MAC: taksonomia Idealny Protokół Wielodostępowy Medium Access Control (MAC): warstwa protokołów wielodostępowych Trzy szerokie klasy protokołów: r Podział łącza Łącze rozgłaszające o przepustowości R b/s 1. Jeśli jeden węzeł chce nadawać, może nadawać z szybkością R. 2. Jeśli M węzłów chce nadawać, każdy może nadawać z średnią przepustowością R/M 3. W pełni rozproszony: m dzielą łącze na mniejsze “kawałki” (szczeliny czasowe, kawałki pasma, według kodu) m przydziela kawałki węzłom do wyłącznego użytku r m nie potrzeba specjalnego węzła do koordynacji podziału Dostęp bezpośredni m łącze nie jest dzielone, kolizje są możliwe łącza m nie potrzeba synchronizacji zegarów, szczelin czasowych m “poprawianie” po kolizji 4. Prosty r “Z kolejnością” m ścisła koordynacja wielodostępu w celu uniknięcia kolizji 5a-5 5a-6 1 Protokoły MAC dzielące łącze: FDMA Protokoły MAC dzielące łącze: TDMA FDMA: frequency division multiple access pasmo łącza jest dzielone na mniejsze pasma każda stacja otrzymuje stałe pasmo częstotliwości r niewykorzystany czas transmisji w nieużywanych pasmach r przykład: sieć lokalna 6 stacji, 1,3,4 mają ramkę, pasma częstotliwości 2,5,6 są niewykorzystane TDMA: time division multiple access r dostęp do łącza w "turach" r każda stacja otrzymuje szczelinę czasową stałej długości (długość = czas transmisji ramki) w każdej turze r nieużywane szczeliny są puste r przykład: sieć lokalna 6 stacji, 1,3,4 mają ramkę, szczeliny 2,5,6 są puste r pasma częstotliwości r tura 5a-7 Kodowanie i dekodowanie CDMA Protokoły MAC dzielące łącze: CDMA nadawca CDMA (Code Division Multiple Access) r r r r r r 5a-8 sygnał wyjściowy Zi,m bity danych każdemu użytkownikowi przypisany jest jednoznaczny “kod”; czyli dzielimy zbiór kodów między użytkowników używany najczęściej w bezprzewodowych łączach rozgłaszających (komórkowych, satelitarnych, itd) wszyscy użytkownicy mają tę samą częstotliwość, ale każdy ma ciąg dzielący dane (kod), które są wysyłane nadmiarowo kodowany sygnał = (oryginalna informacja) X (wartość w ciągu kodu) dekodowanie: suma iloczynów zakodowanego sygnału i wartości w ciągu kodu (wartości w ciągu kodu dodają się do 0) jeśli kody są odpowiednio dobrane, wielu użytkowników może nadawać na tej samej częstotliwości kod odbiorca kod 5a-9 CDMA: dwóch zakłócających nadawców nadawcy bity danych kod 5a-10 Protokoły dostępu bezpośredniego r sygnał wyjściowy Z*i,m Kiedy węzeł ma ramkę do wysłania m transmituje z pełną przepustowością łącza, R. m nie ma koordynacji a priori bity danych kod pomiędzy węzłami dwa lub więcej transmitujących węzłów -> “kolizja” r protokół MAC dostępu bezpośredniego określa: r m jak wykrywać kolizje m jak naprawiać kolizje (n.p., przez opóźnione retransmisje) r Przykłady protokołów MAC dostępu bezpośredniego: m szczelinowe ALOHA m ALOHA odbiorca m CSMA, CSMA/CD, CSMA/CA kod 5a-11 5a-12 2 Szczelinowe ALOHA Szczelinowe ALOHA Założenia Działanie r wszystkie ramki mają ten sam r kiedy węzeł ma nową ramkę, transmituje w rozmiar następnej szczelinie r czas jest podzielony na r jeśli nie ma kolizji, węzeł jednakowe szczeliny (okres może wysłać nową ramkę w czasu na transmitowanie 1 następnej szczelinie ramki) r jeśli jest kolizja, węzeł r węzły zaczynają transmitować retransmituje ramkę w tylko na początku szczelin następnych szczelinach z prawdopodobieństwem p, r węzły są zsynchronizowane aż odniesie sukces r jeśli 2 lub więcej węzłów transmituje w tym samym czasie, wszystkie węzły wykryją kolizję węzeł 1 węzeł 2 węzeł 3 K P K U P K Za r jeden aktywny węzeł może transmitować bez przerwy z pełną przepustowością kanału r wysoce zdecentralizowane: trzeba tylko zsynchronizować szczeliny w węzłach r proste P U U szczeliny Przeciw r kolizje, marnowanie szczelin r puste szczeliny r węzły mogą rozpoznawać kolizje szybciej, niż wynosi czas transmisji ramki 5a-13 Wydajność szczelinowego ALOHA Wydajność jest to stosunek ilości udanych transmisji gdy jest wiele węzłów, z których każdy wysyła wiele ramek, w długim okresie Dla największej wydajności N węzłów, znajdź p* maksymalizujące Np(1-p)N-1 r Załóżmy, że N węzłów wysyła r Dla wielu węzłów, oblicz wiele ramek, każdy wysyła w granicę Np*(1-p*)N-1 szczelinie z prawdopod. p przy N dążącym do niesk., wynik: 1/e =.37 r prawd. że 1szy węzeł ma udaną transmisję = p(1-p)N-1 r prawd. że jakiś węzeł ma W najlepszym razie: udaną transmisję = Np(1-p)N-1 wydajność 37%! 5a-14 Czyste ALOHA (bez szczelin) r r czyste Aloha: prostsze, bez synchronizacji gdy otrzyma się ramkę r prawdopodobieństwo kolizji rośnie: r m transmitować natychmiast m ramka wysłana w czasie t0 koliduje z ramkami wysłanymi w przedziale [t0-1,t0+1] zakłóci początek ramki w. i zakłóci koniec ramki w. i ramka w. i 5a-15 Wydajność czystego ALOHA 5a-16 CSMA (Carrier Sense Multiple Access) P(udana transmisja węzła) = P(węzeł transmituje). P(żaden inny węzeł nie transmituje [t0-1,t0]. = p. (1-p)N-1. (1-p)N-1 = p. (1-p)2(N-1) CSMA: bez synchronizacji, nasłuchiwać przed transmisją: r Jeśli kanał jest wolny: wysyłać całą ramkę r Jeśli kanał jest zajęty, opóźnić transmisję … wybrać najlepsze p i dążąc z n -> nieskończoności... r = 1/(2e) =.18 Ludzka analogia: nie przerywać innym! Jeszcze gorzej ! 5a-17 5a-18 3 Kolizje CSMA CSMA/CD (Collision Detection) Położenie węzłów w przestrzeni kolizje mogą się dalej zdarzać: przestrzeń kolizja: CSMA/CD: nasłuchiwanie, opóźnianie jak w CSMA m kolizje wykrywane w krótkim czasie m kolidujące transmisje są przerywane, co zmniejsza marnowanie kanału czas opóźnienie propagacji powoduje, że dwa węzły mogą nie słyszeć swojej transmisji na czas r wykrywanie kolizji: cały czas transmisji ramki jest zmarnowany m proste w przewodowych sieciach LAN: mierz siłę sygnału, porównaj wysłany, odebrany sygnał uwaga: m trudne w bezprzewodowych sieciach LAN: odbiorca odległość i opóźnienie propagacji mają wpływ na prawdopodobieństwo kolizji odłączony podczas transmisji r analogia ludzka: grzeczny rozmówca 5a-19 Wykrywanie kolizji w CSMA/CD 5a-20 Protokoły MAC "z kolejnością" przestrzeń czas protokoły MAC z podziałem łącza: m przy dużym obciążeniu, dzielą kanał wydajnie i sprawiedliwie m niewydajne przy małym obciążeniu: opóźnienie w dostępie, 1/N przepustowości dostępna nawet, gdy tylko 1 węzeł jest aktywny! protokoły MAC z dostępem bezpośrednim: m wydajne przy małym obciążeniu: pojedynczy węzeł może w pełni wykorzystać kanał m wysokie obciążenie: narzut na kolizje protokoły MAC "z kolejnością": próbują połączyć zalety obu typów! czas wykrycia kolizji (przerwania) 5a-21 5a-22 Protokoły MAC "z kolejnością" Podsumowanie protokołów MAC Odpytywanie: r węzeł nadrzędny kolejno “zaprasza” węzły podrzędne do transmisji r problemy: r Co można zrobić z współdzielonym kanałem? m narzut na odpytywanie m opóźnienie m mała odporność na Przekazywanie żetonu: r żeton kontrolny przekazywany od jednego węzła do drugiego. r komunikat żetonu r problemy: m narzut na żeton m opóźnienie m mała odporność na awarie (żetonu) m Podział kanału, za pomocą czasu, częstotliwości, kodu Time Division, Code Division, Frequency Division m Dostęp bezpośredni (dynamiczny), ALOHA, S-ALOHA, CSMA, CSMA/CD nasłuchiwanie: łatwe w niektórych mediach (przewody), trudne w innych (radio) CSMA/CD używane w Ethernecie m W kolejności awarie (węzła nadrzędnego) odpytywanie z centralnego punktu przekazywanie żetonu 5a-23 5a-24 4 Ethernet Mapa wykładu 5.1 Wprowadzenie i usługi warstwy łącza 5.2 Rozpoznawanie i naprawa błędów 5.3 Protokoły wielodostępowe 5.4 Adresy w sieciach LAN oraz protokół ARP 5.5 Ethernet r r r r r r r r r r “dominująca” technologia LAN: r pierwsza powszechnie używana technologia LAN r Prostsza, tańsza niż sieci LAN z lub ATM r Nadążała za wyścigiem prędkości: 10, 100, 1000, 10000, …, Mb/s 5.6 Koncentratory, mosty, i switche 5.7 Bezprzewodowe łącza i sieci lokalne 5.8 PPP 5.9 ATM 5.10 Frame Relay oryginalny rysunek Metcalfe’a przedstawiający Ethernet 5a-25 5a-26 Struktura ramki Ethernet Struktura ramki Ethernet (c.d.) r Nadający adapter enkapsuluje pakiet IP (lub pakiet innej warstwy sieci) w ramce Ethernet nagłówek adr. adr. odbiorcy nadawcy Adresy: 6 bajtów m jeśli adapter otrzymuje ramkę z adresem MAC adaptera, lub z adresem rozgłaszania (broadcast, n.p. pakiet ARP), przekazuje dane z ramki do protokołu warstwy sieci m w przeciwnym wypadku, adapter wyrzuca ramkę m Chyba że pracuje w trybie promiscuous Dane Typ Typ: wskazuje na protokół warstwy wyższej, zwykle IP ale obsługiwane mogą być również n.p. Novell IPX, AppleTalk) r CRC: sprawdzane u odbiorcy, jeśli jest błąd, to ramka jest wyrzucana r Nagłówek: r 7 bajtów z wzorem 10101010, a potem 1 bajt z wzorem 10101011 r używane do synchronizacji zegarów nadawcy i odbiorcy nagłówek adr. odbiorcy adr. nadawcy Dane Typ 5a-27 5a-28 Zawodna, bezpołączeniowa usługa Bezpołączeniowa: Nie ma sygnalizacji pomiędzy nadającym i odbierającym adapterem. r Zawodna: odbierający adapter nie wysyła ACK ani NAK do nadającego adaptera Ethernet używa CSMA/CD Nie ma szczelin r Zanim adapter rozpocznie adapter nie trasnmituje, jeśli retransmisję, czeka słyszy transmisję innego przez losowy okres adaptera, czyli nasłuchiwanie czasu (carrier sense) r transmitujący adapter przerywa gdy zauważy, że inny adapter transmituje, czyli wykrywanie kolizji (collision detection) r r r m ciąg pakietów przekazywanych do warstwy sieci może mieć luki m luki będą wypełniane, jeśli aplikacja używa TCP m w przeciwnym wypadku, aplikacja będzie musiała sobie radzić sama 5a-29 5a-30 5 Algorytm CSMA/CD w Ethernecie Ethernet’s CSMA/CD (cd…………) 1. Adapter otrzymuje pakiet 4. Jeśli podczas transmisji i tworzy ramkę adapter wykryje inną transmisję, przerywa i 2. Jeśli adapter nie słyszy wysyła sygnał zakłócający transmisji w kanale, zaczyna transmitować 5. Po przerwaniu, adapter ramkę. Jeśli słyszy rozpoczyna wykładnicze transmisję, czeka aż kanał cofanie: po m-tej kolizji, jest wolny i potem adapter wybiera losowo K transmituje z zbioru {0,1,2,…,2m-1}. Adapter czeka 3. Jeśli adapter wyśle całą K*512*(czas na wysłanie ramkę bez wykrycia innej bitu) i wraca do kroku 2 transmisji, to koniec Sygnał zakłócający: zapewnia, że wszyscy nadający dowiedzą się o kolizji; 48 bitów Czas wysłania bitu: 0.1 mikrosekundy dla Ethernetu 10 Mb/s; dla K=1023, czas oczekiwania to około 50 ms Wykładnicze cofanie: r Cel: dostosuj próby retransmisji do estymowanego obciążenia m r r r duże obciążenie: losowy czas oczekiwania będzie dłuższy pierwsza kolizja: wybierz K z {0,1}; opóźnienie K x 512 x czas wysłania bitu po drugiej kolizji: wybierz K z {0,1,2,3}… po dziesięciu kolizjach, wybierz K z {0,1,2,3,4,…,1023} 5a-31 5a-32 Technologie Ethernet: 10Base2 Wydajność CSMA/CD r r Tprop = najdłuższy czas propagacji pomiędzy 2 węzłami w sieci LAN r ttrans = czas na wysłanie najdłuższej ramki 10: 10Mb/s; 2: maksymalna długość kable do 200 cienki kabel koncentryczny, "topologia szyny" r wydajność  połączenie "T" wysłana ramka podróżuje w dwie strony 1 1  5t prop / ttrans węzeł Wydajność rośnie do 1 gdy tprop maleje do 0 Rośnie do 1 gdy ttrans rośnie do nieskończoności r Dużo lepszy niż ALOHA, a nadal zdecentralizowany, prosty, i tani węzeł węzeł węzeł węzeł wzmacniacze (ang. repeater) używane do połączenia wielu interfejsów r wzmacniacz powtarza bity, które słyszy na jednym interfejsie, na pozostałych interfejsach: urządzenie wyłącznie w warstwie fizycznej! 5a-34 r jest to już technologia odziedziczona r r r 5a-33 10BaseT oraz 100BaseT 10BaseT oraz 100BaseT (c.d.) Przepustowość 10/100 Mb/s; ta ostatnia nazywana jest “fast ethernet” r T oznacza "Twisted Pair" r Węzły połączone są z koncentratorem: “topologia gwiazdy”; maksymalna odległość 100 m pomiędzy węzłami i koncentratorem r r Koncentratory to w zasadzie wzmacniacze: m bity wchodzące jednym łączem wychodzą na wszystkich łączach m nie ma buforowania ramek m koncentrator nie używa CSMA/CD: adaptery wykrywają kolizje m udostępnia funkcjonalność zarządzania węzły siecią koncentrator 5a-35 5a-36 6 Kodowanie Manchester Gbit Ethernet r r r r Używane w 10BaseT, 10Base2 Każdy bit ma zmianę sygnału r Pozwala synchronizować zegary nadających i odbierających węzłów r r r r m Ceny rzędu tysięcy złotych (2006) r m nie potrzeba centralnego, globalnego zegara dla tych węzłów! r Ale to są zagadnienia warstwy fizycznej! używa standardowego formatu ramki Ethernet pozwala na łącza punkt-punkt oraz wielodostępowe w trybie wielodostępowym, używa CSMA/CD; wymaga małych odległości między węzłami w celu zwiększenia wydajności używa koncentratorów, zwanych “Buffered Distributors” Full-Duplex z przepustowością 1 Gb/s dla łącz punkt-punkt 10 Gb/s jest już dostępne 5a-37 Listopad 2006: rozpoczęcie prac nad standardem 100 Gb/s 5a-38 7 Plan całości wykładu  Wprowadzenie  Warstwa aplikacji  Warstwa transportu  Warstwa sieci  Warstwa łącza i sieci lokalne  Podstawy ochrony informacji Warstwa Łącza (2 wykłady) (2 wykłady) (2-3 wykłady) (2-3 wykłady) (3 wykłady) (2-3 wykłady) Cele:  zrozumienie zasad działania mechanizmów warstwy łącza:  rozpoznawanie i naprawa błędów  współdzielenie kanału rozgłaszającego: wielodostępowość  adresowanie w warstwie łącza  niezawodna komunikacja, kontrola przepływu: już była o nich mowa!  implementacja różnych technologii warstwy łącza 5a-1 Warstwa łącza: wprowadzenie Mapa wykładu  5.1 Wprowadzenie i usługi warstwy łącza  5.2 Rozpoznawanie i naprawa błędów  5.3 Protokoły wielodostępowe  5.4 Adresy w sieciach LAN oraz protokół ARP  5.5 Ethernet 5a-2 Trochę terminologii:  5.6 Koncentratory, “link”  hosty, rutery, mosty, switche to węzły mosty, i switche  5.7 Bezprzewodowe łącza i sieci lokalne  5.8 PPP  5.9 ATM  5.10 Frame Relay  węzły są połączone łączami  łącza stałe  łącza bezprzewodowe  sieci lokalne  jednostka informacji w warstwie łącza to ramka, która enkapsuluje pakiet warstwa łącza jest odpowiedzialna za za komunikację ramek pomiędzy sąsiednimi węzłami przez łącze 5a-3 Warstwa łącza: kontekst  Pakiety są komunikowane przez różne protokoły warstwy łącza na kolejnych łączach:  n.p., Ethernet na pierwszym łączu, Frame Relay na kolejnych łączach, 802.11 na ostatnim łączu  Każdy protokół w. łącza może oferować różne usługi  n.p., może (lub nie) oferować niezawodną komunikację na łączu 5a-4 Usługi warstwy łącza analogia transportowa  tworzenie ramek, dostęp do łącza (MAC !!!!!!!!):  wycieczka z Warszawy do Bordeaux  limuzyna: z Bristolu na Okęcie  Concorde: Okęcie do Paryża  pociąg: Paryż do Bordeaux  turysta = pakiet  enkapsuluje pakiet w ramce, dodaje nagłówki i zakończenie  uzyskuje dostęp do łącza, jeśli jest współdzielone  ‘adresy fizyczne’ używane w nagłówkach ramek do identyfikacji nadawcy i odbiorcy różne od adresów IP!  Niezawodna komunikacja między sąsiednimi węzłami  w części trzeciej poznaliśmy mechanizmy niezawodnej komunikacji  rzadko używane na łączach, które mają małą stopę błędów (światłowód, jakiś rodzaj kabla)  łącza bezprzewodowe: wysokie stopy błędów Pytanie: po co nam niezawodność na poziomie łącza i na poziomie koniec-koniec (w warstwie transportu)?  etap wycieczki = łącze komunikacyjne  sposób transportu = protokół warstwy łącza  biuro podróży = algorytm rutingu 5a-5 5a-6 1 Komunikacja "adapterów" Usługi warstwy łącza (ciąg dalszy)  Kontrola przepływu: pakiet nadający węzeł  dopasowanie prędkości nadawania i odbierania przez dwa sąsiednie węzły  Rozpoznawanie błędów:  błędy powodowane przez tłumienie lub zakłócenia sygnału sygnalizuje nadawcy konieczność retransmisji, wyrzuca ramkę  Korekcja błędów przez kody nadmiarowe:  odbiorca rozpoznaje i naprawia błędy bitowe bez potrzeby retransmisji  Komunikacja półdupleksowa i w pełni dupleksowa  w komunikacji półdupleksowej (ang. half-duplex, także "nadawanie naprzemienne"), węzły na obu końcach łącza mogą transmitować, ale nie jednocześnie 5a-7 Mapa wykładu usługi warstwy łącza  5.2 Rozpoznawanie i naprawa błędów  5.3 Protokoły wielodostępowe  5.4 Adresy w sieciach LAN oraz protokół ARP  5.5 Ethernet ramka ramka adapter adapter  warstwa łącza jest  odbiorca rozpoznaje błąd:  5.1 Wprowadzenie i odbierający węzeł protokół w. łącza  odbierający adapter  szuka błędów, realizuje niezawodność, kontrolę przepływu, itd  dekapsuluje pakiet,  karta Ethernet, karta PCMCI, przekazuje warstwie karta 802.11 odbierającemu węzłowi implementowana w “adapterach” (tzw. NIC, Network Interface Card)  nadający adapter:  adapter jest częściowo  enkapsuluje pakiet w ramce autonomiczny  dodaje bity sum kontrolnych,  działa w w. łącza i fizycznej niezawodność, kontrolę przepływu, itd. 5a-8 Technologie LAN Co wiemy już o warstwie łącza:  5.6 Koncentratory,  usługi, wykrywanie/korekcja błędów, protokoły mosty, i switche  5.7 Bezprzewodowe łącza i sieci lokalne  5.8 PPP  5.9 ATM  5.10 Frame Relay wielodostępowe Dalej: technologie LAN  adresowanie  Ethernet  koncentratory (hub), mosty (bridge), switche  802.11  PPP  ATM 5a-9 Adresy LAN oraz ARP 5a-10 Adresy LAN oraz ARP Każdy adapter w sieci LAN ma niepowtarzalny adres LAN 32-bitowy adres IP:  adres warstwy sieci węzeł  stosowany do przekazania pakietu do sieci IP odbiorcy (przypomnij definicję sieci IP) adres LAN (albo MAC albo fizyczny albo Ethernet):  stosowany do przekazania ramki pomiędzy węzeł węzeł interfejsami połączonymi w warstwie łącza (w tej samej sieci)  48-bitowy adres MAC (dla większości sieci LAN) wypalony w pamięci ROM adaptera węzeł 5a-11 5a-12 2 Adresy LAN (więcej) Przypomnienie dyskusji o rutingu Zaczynając w A, przekazywanie pakietu IP do B:  przydzielanie adresów MAC zarządzane przez IEEE  producent kupuje przedział adresów MAC (co zapewnia jednoznaczność)  Analogia: (a) adres MAC: jak numer NIP (b) adres IP: jak adres pocztowy  płaskie adresy MAC => przenośność A  znajdź adres IP B: jest w tej 223.1.1.1 223.1.2.1 223.1.1.2 223.1.1.4 223.1.2.9 B samej sieci co A 223.1.1.3  warstwa łącza wysyła pakiet do B w ramce w-stwy łącza adres nadawcy, odbiorcy ramki adr. MAC adr. MAC B A  można przenieść kartę LAN z jednej sieci LAN do drugiej  hierarchiczne adresy IP NIE SĄ przenośne  zależą od sieci IP, do której podłączony jest węzeł adres nadawcy, odbiorcy pakietu adr. IP adr. IP A B 223.1.3.27 223.1.2.2 dane IP pakiet ramka 5a-13 ARP: Address Resolution Protocol Pytanie: jak poznać adres MAC B znając adres IP B? węzeł węzeł  Każdy węzeł IP (host, ruter) w sieci LAN ma tablicę ARP  Tablica ARP: odwzorowanie adresów IP/MAC dla niektórych węzłów w sieci LAN  węzeł 5a-14 Protokół ARP węzeł TTL (Time To Live): czas, po którym odwzorowanie zostanie zapomniane (zwykle 20 minut)  A chce posłać pakiet do B, A zna adres IP B.  Załóżmy, że adres MAC B nie jest w tablicy ARP A.  A rozgłasza pakiet z pytaniem ARP, zawierający adres IP B  wszystkie węzły w sieci LAN otrzymują pytanie ARP  B otrzymuje pakiet ARP, odpowiada A podając swój adres MAC  A wysyła ramkę na adres MAC B  A zachowuje odwzorowanie adresów IP-na-MAC w swojej tablicy ARP, dopóki informacja się nie zestarzeje  miękki stan (soft state): informacja jest zapominana (znika), jeśli nie zostanie odświeżona  ARP jest “plug-and-play”:  węzły tworzą tablice ARP bez interwencji administratora sieci 5a-15 Ruting do innej sieci LAN A 5a-16  A tworzy pakiet z adr. nadawcy A, adr. odbiorcy B  A używa ARP by poznać adres MAC interfejsu rutera krok po kroku: wyślij pakiet od A do B przez R zakładamy, że A zna adres IP B 111.111.111.110  A tworzy ramkę w-stwy łącza z adresem MAC rutera R jako odbiorcą, ramka zawiera pakiet A-B  W-stwa łącza A wysyła ramkę węzeł węzeł E 223.1.3.2 223.1.3.1  W-stwa łącza R odbiera ramkę  R usuwa pakiet IP z ramki Ethernet, widzi, że odbiorcą jest B ruter  R używa ARP by poznać fizyczny adres B R węzeł B węzeł  R tworzy ramkę zawierającą pakiet A-B, którą wysyła do B  Dwie tablice ARP w ruterze R, po jednej dla każdej sieci ruter  W tablicy rutingu u nadawcy znajduje się adres rutera, 111.111.111.110  W tablicy ARP u nadawcy znajduje się adres MAC rutera, 5a-17 E6-E9-00-17-BB-4B węzeł A węzeł R węzeł B węzeł 5a-18 3 Mapa wykładu  Usługi warstwy Warstwa transportu  Transport połączeniowy: transportu  Multipleksacja i demultipleksacja  Transport bezpołączeniowy: UDP  Zasady niezawodnej komunikacji danych TCP  struktura segmentu  niezawodna komunikacja  kontrola przepływu  zarządzanie połączeniem  Mechanizmy kontroli przeciążenia  Kontrola przeciążenia w TCP 3-1 TCP: Przegląd Struktura segmentu TCP RFC: 793, 1122, 1323, 2018, 2581  komunikacja "full duplex":  koniec-koniec: 32 bity  dwukierunkowy przepływ  jeden nadawca, danych na tym samym połączeniu  MRS: maksymalny rozmiar segmentu jeden odbiorca  niezawodny, uporządkowany strumień bajtów:  nie ma “granic komunikatów”  wysyłający grupowo:  połączeniowe: komunikatów kontrolnych) połączenia przed komunikacją danych TCP określają rozmiar okna bufory u nadawcy i odbiorcy  kontrola przepływu: odbiorcy aplikacja czyta dane TCP bufor nadawcy TCP bufor odbiorcy port nadawcy # port odbiorcy # numer sekwencyjny ACK: numer ACK używane licząc według bajtów danych (nie segmentów!) numer potwierdzenia dług. nie nagł. używ. UAPRSF Okno odbiorcy suma kontrolna RST, SYN, FIN: zarządzanie połączeniem (polecenia nawiązania i zamknięcia)  nadawca nie "zaleje" aplikacja pisze dane URG: pilne dane (zwykle nie używane) PSH: wypchnij dane  inicjalizacja (wymiana  kontrola przeciążeń i przepływu  3-2 Wsk. na pilne dane Opcje (zmienna długość) Internetowa ilość bajtów, jakie przyjmie odbiorca dane aplikacji (zmienna długość) suma kontrolna (jak w UDP) gniazdo gniazdo segment 3-3 TCP: numery sekwencyjne i potwierdzenia 3-4 TCP: czas powrotu (RTT) i timeout Numery sekwencyjne: Host B Host A  numer w "strumieniu bajtów" pierwszego bajtu Użytkownik danych segmentu wpisuje Potwierdzenia: Host B ‘C’ potwierdza  numer sekwencyjny ‘C’, wysyła następnego bajtu z powrotem oczekiwanego od drugiej ‘C’ strony  kumulatywny ACK host A Pytanie: jak odbiorca traktuje potwierdza segmenty nie w kolejności odbiór  O: specyfikacja TCP tego ‘C’ nie określa: decyduje implementacja otrzymanego czas od hosta B prosty scenariusz telnet 3-5 Pytanie: jak ustalić timeout dla TCP?  dłuższe niż RTT  ale RTT jest zmienne  za krótki: za wczesny timeout  niepotrzebne retransmisje  za długi: wolna reakcja na stratę segmentu Pytanie: jak estymować RTT?  MierzoneRTT: czas zmierzony od wysłania segmentu do odbioru ACK  ignorujemy retransmisje  MierzoneRTT będzie zmienne, chcemy mieć "gładsze" estymowane RTT  średnia z wielu ostatnich pomiarów, nie tylko aktualnego MierzoneRTT 3-6 1 TCP: czas powrotu (RTT) i timeout Przykład estymacji RTT: RTT: gaia.cs.umass.edu to fantasia.eurecom.fr EstymowaneRTT = (1- )*EstymowaneRTT + *MierzoneRTT 350  Wykładnicza średnia ruchoma 300 RTT (milliseconds)  wpływ starych pomiarów maleje wykładniczo  typowa wartość parametru:  = 0.125 250 200 150 100 1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106 time (seconnds) SampleRTT Estimated RTT 3-7 TCP: czas powrotu (RTT) i timeout Ustawianie timeout 3-8 Mapa wykładu  Usługi warstwy  EstymowaneRTT dodać “margines błędu” transportu  Multipleksacja i demultipleksacja  Transport bezpołączeniowy: UDP  Zasady niezawodnej komunikacji danych  im większa zmienność MierzoneRTT, tym większy margines błędu  najpierw ocenić, o ile MierzoneRTT jest oddalone od EstymowaneRTT: BłądRTT = (1-)*BłądRTT + *|MierzoneRTT - EstymowaneRTT| (zwykle,  = 0.25)  Transport połączeniowy: TCP  struktura segmentu  niezawodna komunikacja  kontrola przepływu  zarządzanie połączeniem  Mechanizmy kontroli przeciążenia  Kontrola przeciążenia w TCP Ustalanie wielkości timeout: Timeout = EstymowaneRTT + 4*BłądRTT 3-9 Zdarzenia nadawcy TCP: Niezawodna komunikacja TCP  TCP tworzy usługę NPK na zawodnej komunikacji IP  Wysyłanie grupowe segmentów  Kumulowane potwierdzenia  TCP używa pojedynczego zegara do retransmisji 310  Retransmisje są powodowane przez:  zdarzenia timeout  duplikaty ACK  Na razie rozważymy prostszego nadawcę TCP:  ignoruje duplikaty ACK  ignoruje kontrolę przeciążenia i przepływu 311 Dane od aplikacji: Timeout:  Utwórz segment z numerem  retransmituj segment, sekwencyjnym który spowodował timeout  numer sekwencyjny to numer w  ponownie włącz zegar strumieniu bajtów pierwszego bajtu danych segmentu Odbiór ACK:  włącz zegar, jeśli jest wyłączony  Jeśli potwierdza (zegar działa dla najstarszego niepotwierdzone niepotwierdzonego segmentu) segmenty:  oblicz czas oczekiwania: Timeout  potwierdź odpowiednie segmenty  włącz zegar, jeśli są brakujące segmenty 312 2 } TCP: scenariusze retransmisji Host A Host A Host B timeout numeru 92 Host B X strata Pocz_Okna = 100 zdarzenie: Odbiór ACK potwierdzającego pakiet y if ( y > Pocz_Okna ) { Pocz_Okna = y; if ( są niepotwierdzone segmenty w oknie ) włącz zegar; } } Pocz_Okna = 120 Pocz_Okna = 100 timeout numeru 92 zdarzenie: Timeout retransmituje niepotwierdzony segment o najniższym numerze sekwencyjnym; włącz zegar; Komentarz: Pocz_Okna - 1: ostatni potwierdzony bajt Przykład: Pocz_Okna - 1 = 71; y= 73, więc odbiorca chce bajty powyżej 73; y > Pocz_Okna, więc nowe dane zostały potwierdzone timeout Nadawca TCP (uproszczony) Nast_Num = 1 Pocz_Okna = 1 loop (forever) { switch( zdarzenie ) { zdarzenie: Dane od aplikacji stwórz segment z numerem Nast_Num; if ( zegar wyłączony ) włącz zegar; przekaż segment do warstwy IP; Nast_Num = Nast_Num + length( dane ); Pocz_Okna = 120 czas czas scenariusz ze stratą ACK za wczesny timeout 3-13 Wysyłanie ACK w TCP [RFC 1122, RFC 2581] TCP: scenariusze retransmisji (c.d.) timeout Host A 314 Host B X strata Pocz_Okna = 120 Zdarzenie u odbiorcy TCP Akcja odbiorcy TCP Odbiór segmentu o oczekiwanym numerze w kolejności. Wszystkie poprzednie dane już potwierdzone Opóźnione ACK. Czekaj do 500 ms na następny segment. Jeśli go nie ma, wyślij ACK. Odbiór segmentu o oczekiwanym numerze w kolejności. Jeden inny segment nie był potwierdzony Wyślij natychmiast skumulowane ACK, potwierdzające oba segmenty. Odbiór segmentu nie w kolejności o za wysokim numerze. Wykrycie luki w danych Wyślij natychmiast duplikat ACK, w którym podany jest numer oczekiwanego bajtu czas Odbiór segmentu, który całkiem lub częściowo wypełnia lukę. Skumulowany ACK Jeśli segment leży na początku luki, wyślij natychmiast ACK. 316 315 Szybkie retransmisje  Okres oczekiwania na timeout jest długi:  długie czekanie na retransmisje  Rozpoznaj stracone segmenty przez duplikaty ACK.  Nadawca często wysyła segmenty jeden tuż po drugim  Jeśli segment zginie, może być wiele duplikatów ACK. Algorytm szybkich retransmisji:  Jeśli nadawca otrzyma 3 duplikaty ACK dla tych samych danych, zakłada, że następny segment po potwierdzonych danych zginął: zdarzenie: Odbiór ACK potwierdzającego pakiet y if ( y > Pocz_Okna ) { Pocz_Okna = y; if ( są niepotwierdzone segmenty w oknie ) włącz zegar; } else { zwiększ licznik duplikatów ACK dla y; if ( licznik duplikatów ACK dla y == 3 ) retransmituj segment y; }  szybkie retransmisje: wyślij segment zanim nastąpi timeout duplikat ACK dla już potwierdzonego segmentu szybka retransmisja 3-17 318 3 Kontrola przepływu TCP Mapa wykładu  Usługi warstwy  Transport połączeniowy:  Multipleksacja i  struktura segmentu transportu  odbiorca TCP ma bufor odbiorcy: TCP demultipleksacja  Transport bezpołączeniowy: UDP  Zasady niezawodnej komunikacji danych Okno odbiorcy TCP  niezawodna komunikacja  kontrola przepływu Dane od warstwy IP  zarządzanie połączeniem Wolne miejsce Dane TCP w buforze Dane do warstwy aplikacji  Mechanizmy kontroli przeciążenia Bufor TCP  Kontrola przeciążenia w  usługa dopasowania prędkości: dopasuje prędkość TCP wysyłania aplikację do prędkości odbioru danych przez 319 Jak działa kontrola przepływu TCP Mapa wykładu Okno odbiorcy TCP Dane od warstwy IP Dane TCP w buforze Wolne miejsce 320  Usługi warstwy Dane do warstwy aplikacji Bufor TCP Załóżmy, że odbiorca wyrzuca segmenty nie w kolejności.  Odbiorca ogłasza wolne miejsce umieszczając jego wielkość w segmentach ACK  Odbiorca ogranicza rozmiar okna do wolnego miejsca transportu  Multipleksacja i demultipleksacja  Transport bezpołączeniowy: UDP  Zasady niezawodnej komunikacji danych  Transport połączeniowy: TCP  struktura segmentu  niezawodna komunikacja  kontrola przepływu  zarządzanie połączeniem  Mechanizmy kontroli przeciążenia  Kontrola przeciążenia w TCP  gwarantuje, że bufor nie zostanie przepełniony 321 Zarządzanie połączeniem TCP odbiorca TCP, tworzą “połączenie” zanim wymienią dane  inicjalizacja zmiennych TCP:  numery sekwencyjne  bufory, informacja kontroli przepływu (rozmiar bufora)  klient: nawiązuje połączenie Socket clientSocket = new Socket("hostname","port number");  serwer: odbiera połączenie Socket connectionSocket = welcomeSocket.accept(); Zarządzanie połączeniem TCP (c.d..) Trzykrotny uścisk dłoni: Zamykanie połączenia: Krok 1: host klienta wysyła segment SYN do serwera  podaje początkowy numer sekwencyjny  bez danych klient zamyka gniazdo: clientSocket.close(); zamnknij klient serwer gniazdo Krok 1: Host klienta wysyła Krok 2: host serwera odbiera SYN, odpowiada segmentem SYNACK segment TCP FIN do serwera  serwer alokuje bufory  określa początkowy numer Krok 3: klient odbiera SYNACK, odpowiada segmentem ACK, który może zawierać dane zamknij gniazdo Krok 2: serwer odbiera FIN, odpowiada segmentem ACK. Zamyka połączenie, wysyła FIN. timeout Przypomnienie: Nadawca i 322 połączenie zamknięte połączenie zamknięte 323 324 4 Zarządzanie połączeniem TCP (c.d..) Zarządzanie połączeniem TCP (c.d.) aplikacja klienta otwiera połączenie wyślij SYN ZAMKNIĘTE minęło 30s Krok 3: klient odbiera FIN, klient odpowiada segmentem ACK. zamknij  Rozpoczyna oczekiwanie- CZEKAJ odebrano FIN wyślij ACK serwer gniazdo POŁĄCZONY aplikacja klienta zamyka połączenie wyślij FIN FIN-CZEKAJ zamknij gniazdo Krok 4: serwer odbiera ACK. 1 timeout SŁUCHANIE odebrano SYN wyślij SYN-ACK OSTATNI ACK połączenie zamknięte wyślij FIN ZAMKNIJ CZEKAJ ODEBRANY SYN odebrano ACK Odebrano FIN wyślij ACK 325 POŁĄCZONY 326 Zasady kontroli przeciążenia Mapa wykładu transportu  Multipleksacja i demultipleksacja  Transport bezpołączeniowy: UDP  Zasady niezawodnej komunikacji danych aplikacja serwera tworzy gniazdo czekające odebrano ACK połączenie zamknięte  Usługi warstwy Cykl życia serwera TCP ZAMKNIĘTE Cykl życia klienta TCP Połączenie zamknięte. obsługuje jednoczesne FIN. odebrano SYN-ACK wyślij ACK FIN-CZEKAJ 2 odebrano ACK będzie odpowiadał ACK na otrzymane FIN. Uwaga: z małymi zmianami, WYSŁANY SYN Przeciążenie:  Transport połączeniowy:  nieformalnie: “za wiele źródeł wysyła za wiele TCP danych za szybko, żeby sieć mogła je obsłużyć”  struktura segmentu  różni się od kontroli przepływu!  niezawodna komunikacja  objawy przeciążenia:  kontrola przepływu  zgubione pakiety (przepełnienie buforów w  zarządzanie połączeniem ruterach)  Mechanizmy kontroli  duże (i zmienne) opóźnienia (kolejkowanie w przeciążenia  Kontrola przeciążenia w TCP buforach ruterów)  jeden z głównych problemów sieci!  konsekwencja braku kontroli dostępu do sieci 327 328 Przyczyny/koszty przeciążenia: scenariusz 1 Przyczyny/koszty przeciążenia: scenariusz 2 Host A  dwóch nadawców, Host B lout lin : orginalne dane  jeden ruter, skończone bufory  retransmisje straconych pakietów nieskończony bufor łącza wyjściowego Host l : oryginalne dane A l' : oryginalne dane plus in lout in retransmisje opóźnienie dwóch odbiorców  jeden ruter, nieskończone bufory  bez retransmisji  duże opóźnienia przy przeciążeniu Host B skończone, współdzielone bufory łącza wyjściowego  maksymalna dostępna przepustowość 329 330 5 Przyczyny/koszty przeciążenia: scenariusz 2 Przyczyny/koszty przeciążenia: scenariusz 3  czterech nadawców  zawsze: (goodput)  dłuższe ścieżki  “doskonałe” retransmisje tylko po stracie: l  timeout/retransmisje in  retransmisje opóźnionych (nie straconych) pakietów zwiększa l in lout (w porównaniu z doskonałymi) dla tego samego goodput lout lin : oryginalne dane Host A l'in : oryginalne dane plus retransmisje skończone, współdzielone bufory łącza wyjściowego Host B 331 Przyczyny/koszty przeciążenia: scenariusz 3 332 Metody kontroli przeciążenia Dwa rodzaje metod kontroli przeciążenia: H os t A l o u t Kontrola przeciążenia typu koniec-koniec: Kontrola przeciążenia z pomocą sieci:  brak bezpośredniej  rutery udostępniają informację informacji zwrotnej od warstwy sieci  przeciążenie jest obserwowane na podstawie strat i opóźnień w systemach końcowych  tą metodą posługuje się TCP H os t B zwrotną systemom końcowym  pojedynczy bit wskazuje na przeciążenie (SNA, DECbit, TCP/IP ECN, ATM)  podawana jest dokładna prędkość, z jaką system końcowy powinien wysyłać 333 Studium przypadku: kontrola przeciążeń w usłudze ABR sieci ATM ABR: available bit rate:  “usługa elastyczna”  jeśli ścieżka nadawcy jest “niedociążona”:  nadawca powinien używać dostępną przepustowość  jeśli ścieżka nadawcy jest przeciążona:  nadawca jest ograniczany do minimalnej gwarantowanej przepustowości Komórki RM (resource management): 334 Studium przypadku: kontrola przeciążeń w usłudze ABR sieci ATM nadawca  wysyłane przez nadawcę, przeplatane z komórkami danych  bity w komórce RM ustawiane przez przełączniki sieci (“z pomocą sieci”)  bit NI: nie zwiększaj szybkości (lekkie przeciążenie)  bit CI: wskazuje na przeciążenie  komórki RM zwracane są do nadawcy przez odbiorcę bez zmian komórki RM komórki danych odbiorca  dwubajtowe pole ER (explicit rate) w komórce RM  przeciążony switch może zmniejszyć wartość ER w komórce  z tego powodu, nadawca ma minimalną dostępną przepustowość na ścieżce  bit EFCI w komórkach danych: ustawiany na 1 przez przeciążony switch  jeśli komórka danych poprzedzająca komórkę RM ma ustawiony bit EFCI, odbiorca ustawia bit CI w zwróconej komórce RM 335 336 6 Kontrola przeciążenia w TCP Mapa wykładu  metoda koniec-koniec (bez  Usługi warstwy  Transport połączeniowy:  Multipleksacja i  struktura segmentu transportu demultipleksacja  Transport bezpołączeniowy: UDP  Zasady niezawodnej komunikacji danych pomocy sieci)  nadawca ogranicza prędkość transmisji: TCP OstatniWysłanyBajtOstatniPotwierdzonyBajt  RozmiarOkna  niezawodna komunikacja  kontrola przepływu  zarządzanie połączeniem  Z grubsza,  Mechanizmy kontroli przeciążenia  RozmiarOkna jest zmienny,  Kontrola przeciążenia w funkcja obserwowanego przeciążenia sieci TCP Jak nadawca obserwuje przeciążenie?  strata = timeout lub 3 zduplikowane ACK  nadawca TCP zmniejsza prędkość (RozmiarOkna) po stracie trzy mechanizmy:  AIMD  powolny start  konserwatywne po zdarzeniu timeout 337 Mechanizm AIMD w TCP multiplikatywne zmniejszanie: dziel RozmiarOkna przez dwa po stracie rozmiar okna przeciazenia 24 Kb 338 Powolny start TCP addytywne zwiększanie: dodawaj 1 do RozmiarOkna jeżeli nie było stratyzmiar segmentu po każdym RTT bez straty: badanie sieci  Po nawiązaniu połączenia, RozmiarOkna = 1 segment  Przykład: Segment = 500 b oraz RTT = 200 ms  początkowa prędkość = 2.5 kb/s  dostępna przepustowość >> rozmiarSegmentu/RTT  pożądane jest szybkie przyśpieszenie komunikacji 16 Kb 8 Kb czas Długotrwałe połączenie TCP 339 Udoskonalenie powolnego startu Powolny start TCP (c.d.)  Po nawiązaniu połączenia,  podwajaj RozmiarOkna co  Po 3 zduplikowanych ACK: Host A  RozmiarOkna dzielimy przez dwa Host B  okno zwiększane liniowo RTT zwiększaj prędkość wykładniczo do pierwszej straty: 340  Ale: po zdarzeniu timeout:  RozmiarOkna ustawiany na 1 segment; RTT  okno z początku zwiększane wykładniczo  osiągane przez zwiększanie RozmiarOkna po otrzymaniu ACK  do pewnej wielkości, potem zwiększane liniowo  Podsumowanie: początkowo, prędkość jest mała, ale szybko przyśpiesza czas 341 342 7 Pytanie: Kiedy przestać zwiększać okno wykładniczo, a zacząć zwiększać liniowo? Odpowiedź: Gdy RozmiarOkna osiągnie połowę swojej wartości z przed zdarzenia timeout. Rozmiar Okna Udoskonalenia (c.d.) Podsumowanie: kontrola przeciążenia TCP  Gdy RozmiarOkna poniżej wartości Próg, nadawca w stanie powolnego startu, okno rośnie wykładniczo. Próg  Gdy RozmiarOkna powyżej wartości Próg, nadawca w stanie unikania przeciążenia, okno rośnie liniowo. Próg  Po trzech zduplikowanych ACK, Próg = RozmiarOkna/2 oraz RozmiarOkna = Próg. Czas mierzony w RTT Implementacja:  Po zdarzeniu timeout, Próg = RozmiarOkna/2 oraz  Zmienny Próg RozmiarOkna = 1 segment.  Po stracie, Próg jest ustalany na 1/2 wartości RozmiarOkna tuż przed stratą 343 Podsumowanie: kontrola przeciążenia TCP 344 Przepustowość TCP Zdarzenie Stan Akcja nadawcy TCP Komentarz Odebranie ACK za niepotwierdzone dane Powolny Start (PS) RozmiarOkna = RozmiarOkna + 1 segment, If (RozmiarOkna > Próg) stan = “Unikanie Przeciążenia” Po upływie RTT, RozmiarOkna się podwaja Odebranie ACK za niepotwierdzone dane Unikanie Przeciążenia (UP) RozmiarOkna = RozmiarOkna + (1 segment / RozmiarOkna) Liniowy wzrost RozmiarOkna o 1 segment po upływie RTT  Niech W będzie rozmiarem okna w chwili Strata zaobserwowana przez 3 zduplikowane ACK PS lub UP Próg = RozmiarOkna / 2, RozmiarOkna = Próg, Stan = “Unikanie Przeciążenia” Szybka poprawa przez multiplikatywne zmniejszanie. RozmiarOkna nie będzie mniejszy niż 1 segment.  Gdy okno ma rozmiar W, przepustowość Timeout PS lub UP Próg = RozmiarOkna/2, RozmiarOkna = 1 segment, Stan = “Powolny Start” Wchodzimy w Powolny Start  Zaraz po stracie, okno zmniejszane do Zduplikowany ACK PS lub UP Zwiększ licznik ACK dla potwierdzonego segmentu RozmiarOkna ani Próg nie zmieniają się.  Jaka jest średnia przepustowość TCP jako funkcja rozmiaru okna oraz RTT?  Ignorujemy powolny start straty. jest W/RTT W/2, przepustowość jest W/2RTT.  Średnia przepustowość: ¾ W/RTT 345 346 Przyszłość TCP Sprawiedliwość TCP  Przykład: segment 1500 bajtów, RTT 100ms, Sprawiedliwy cel: jeśli K połączeń TCP dzieli to samo łącze o przepustowości R będące wąskim gardłem, każde połączenie powinno mieć średnią przepustowość R/K chcemy przepustowość 10 Gb/s  Potrzeba rozmiaru okna W = 83 333 segmentów  Przepustowość jako funkcja częstości strat L: Połączenie TCP 1 1.22  segment RTT L  ➜ L = 2·10-10 Bardzo wyśrubowana!  Potrzeba nowych wersji TCP dla bardzo szybkich Połączenie TCP 2 sieci! 347 ruter będący wąskim gardłem: przepustowość R 348 8 Więcej o sprawiedliwości Dlaczego TCP jest sprawiedliwe? Dwa konkurujące połączenia:  addytywne zwiększanie daje nachylenie 1, gdy rośnie przepustowość  multiplikatywne zmniejszanie zmniejsza przepustowość proporcjonalnie równe udziały przepustowości R strata: zmniejsz okno dwukrotnie unikanie przeciążenia: liniowy wzrost Przepustowość połączenia 1 Sprawiedliwość i równoległe Sprawiedliwość i UDP połączenia TCP  Komunikacja strumieniowa nie  nic nie powstrzyma aplikacji przed używa TCP nawiązaniem równoległych połączeń  nie chce zmieniać prędkości pomiędzy 2 hostami. nadawania zgodnie z kontrolą przeciążeń  Robią tak przeglądarki WWW  W zamian używa UDP:  Przykład: łącze o przepustowości R obsługuje 9 połączeń;  śle audio/wideo ze stałą prędkością, toleruje straty pakietów  nowa aplikacja prosi o 1 połączenie  Obszar badań: Komunikacja  nowa aplikacja prosi o 11 połączeń strumieniowa "TCP friendly" TCP, dostaje przepustowość R/10 TCP, dostaje przepustowość R/2 ! R 349 350 Podsumowanie warstwy transportu  mechanizmy usług warstwy transportu:  multipleksacja, demultipleksacja  niezawodna komunikacja  kontrola przepływu  kontrola przeciążenia  w Internecie:  UDP  TCP Co dalej:  opuszczamy “brzeg” sieci (warstwy aplikacji i transportu)  wchodzimy w “szkielet” sieci 351 9 Plan całości wykładu  Wprowadzenie  Warstwa aplikacji  Warstwa transportu  Warstwa sieci  Warstwa łącza i sieci lokalne  Podstawy ochrony informacji (2 wykłady) (2 wykłady) (2-3 wykłady) (2-3 wykłady) (3 wykłady) (2-3 wykłady) 4-1 1 Warstwa sieci Cele: Przegląd:  zrozumienie zasad i  usługi warstwy sieci problemów działania usług  zasady działania rutingu: wybór warstwy sieci: tras  rutingu (wyboru tras)  ruting hierarchiczny  skalowalności sieci  IP  jak działa ruter  Protokoły rutingu w Internecie  zaawansowane tematy: IPv6, mobilność  implementacja tych zasad w Internecie   wewnętrzne zewnętrze  co się dzieje w ruterze?  IPv6  mobilność 4-2 2 1 Mapa wykładu 4.1 Usługi warstwy sieci z komutacją pakietów 4.2 Zasady działania rutingu 4.3 Ruting hierarchiczny 4.4 Protokół Internetu (IP) 4.5 Ruting w Internecie 4.6 Co jest w ruterze 4.7 IPv6 4.8 Ruting rozsiewczy (multicast) 4.9 Mobilność 4-3 3 Usługi warstwy sieci z komutacją pakietów  skierować pakiet od hosta nadawcy do hosta odbiorcy  protokoły warstwy sieci są w każdym hoście, ruterze Podstawowe funkcje:  wybór ścieżki: ścieżka, którą przebędzie pakiet od nadawcy do odbiorcy. Algorytmy rutingu  przekazywanie: przesłanie pakietu z wejścia rutera do odpowiedniego wyjścia rutera application transport network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical application transport network data link physical 4-4 4 2 Model usług sieciowych Pytanie: Jaki jest model usługi sieci przesyłającej pakiety od nadawcy do odbiorcy?  best-effort?  gwarantowana przepustowość?  synchronizacja czasowa (zachowanie odstępów czasowych)?  niezawodna komunikacja?  uporządkowana komunikacja?  informowanie nadawcy o przeciążeniu? komutacja wg słownika języka polskiego: 1. «proces automatycznego przełączania obwodów elektrycznych za pomocą komutatora» 2. «zastąpienie jednostki językowej w wyrażeniu inną jednostką należącą do tej samej klasy» Najważniejsze modele usług warstwy sieci z komutacją pakietów: Sieci z komutacją pakietów ? Sieci z wirtualnymi kanałami ? Sieci datagramowe 4-5 5 Wirtualne kanały “ścieżka od nadawcy do odbiorcy zachowuje się jak kanał telefoniczny”  z punktu widzenia wydajności  czynności warstwy sieci dotyczą ścieżki od nadawcy do odbiorcy  inicjalizacja wirtualnego kanału zanim nastąpi komunikacja danych  każdy pakiet ma identyfikator wirtualnego kanału (nie identyfikator odbiorcy!)  każdy ruter na ścieżce nadawca-odbiorca utrzymuje “stan” dla każdego wirtualnego kanału  połączenia w w. transportu angażowały tylko dwa hosty  zasoby łącz i ruterów (przepustowość, bufory) mogą być przydzielane do wirtualnych kanałów  żeby uzyskać wydajność jak w kanale telefonicznym 4-6 6 3 Wirtualne kanały: protokoły sygnalizacyjne  używane do inicjalizacji, zarządzania, zamykania wirtualnego kanału  używane w sieciach ATM, Frame-Relay, X.25  nie używane w dzisiejszym Internecie? aplikacji 5. Rozpoczęcie komunikacji transportu danych 4. Połączony sieci 1. Połączenie łącza fizyczna 6. Odbieranie danych aplikacji 3. Przyjęcie transportu połączenia sieci 2. Przychodzące łącza połączenie fizyczna 4-7 7 Sieci datagramowe: model Internetu  nie są tworzone połączenia w warstwie sieci  rutery: nie przechowują stanu o połączeniach koniec-koniec  w warstwie sieci nie jest używane pojęcie "połączenia"!  pakiety przekazywane przy użyciu adresu odbiorcy  pakiety między tym samym nadawcą i odbiorcą mogą korzystać z różnych ścieżek aplikacji transportu sieci łącza fizyczna 1. Wyślij informację 2. Odbierz informację aplikacji transportu sieci łącza fizyczna 4-8 8 4 Modele usług warstwy sieci: Gwarancje ? Architektura sieci Internet Model usług Przepustowość Brak Synchro- Informacja o strat Porządek nizacja przeciążeniu best effort brak nie nie nie ATM CBR stała tak tak tak ATM VBR tak tak ATM ABR tak nie ATM UBR gwarantotak wana gwarantonie wane minimum brak nie tak nie nie (wnioskowana ze strat) nie ma przeciążenia nie ma przeciążenia tak nie CBR constant bit rate VBR variable bit rate ABR available bit rate UBR unspecified bit rate 4-9 9 Różnice pomiędzy sieciami z wirtualnymi kanałami i sieciami datagramowymi Internet ATM  komunikacja danych pomiędzy  wywodzi się ze telefonii komputerami  rozmowy głosowe:  usługi “elastyczne”, nie ma  potrzeba potrzeby synchronizacji. synchronizacji, małego  “sprytne” systemy końcowe opóźnienia (komputery)  potrzeba  mogą się dostosować, gwarantowanych usług sterować, naprawiać błędy  “głupie” systemy końcowe  proste działanie szkieletu  telefony sieci, złożoność na  złożoność w działaniu “brzegu” "szkieletu" sieci  wiele typów łącz  różne charakterystyki  trudno o jednolitą usługę 4-10 10 5 Mapa wykładu  4.1 Usługi warstwy sieci z komutacją pakietów  4.2 Zasady działania rutingu  4.3 Ruting hierarchiczny  4.4 Protokół Internetu (IP)  4.5 Ruting w Internecie  4.6 Co jest w ruterze  4.7 IPv6  4.8 Ruting rozsiewczy (multicast)  4.9 Mobilność 4-11 11 Ruting Protokół rutingu 5 Cel: znajdź “dobrą” ścieżkę (ciąg ruterów) przez sieć od nadawcy do odbiorcy. Abstrakcyjne przedstawienie rutingu na grafach:  węzłami grafu są rutery  krawędziami grafu są łącza sieci  koszt krawędzi: opóźnienie, koszt pieniężny, lub obciążenie 2 A B 2 1 D 3 C 3 1 5 F 1 E 2  “dobra” ścieżka:  zwykle ścieżka o najmniejszym koszcie  inne definicje są możliwe 4-12 12 6 Klasyfikacja algorytmów rutingu Informacja globalna czy zdecentralizowana? Globalna:  wszystkie rutery mają pełną topologię sieci, koszty łącz  algorytmy “stanu łącza” Zdecentralizowana:  ruter zna swoich sąsiadów, koszty łącz do sąsiadów  iteracyjny proces obliczania, wymiana informacji z sąsiadami  algorytmy “wektora odległości” Statyczne czy dynamiczne? Statyczne:  ścieżki zmieniają się niezbyt często Dynamiczne:  ścieżki zmieniają się częściej  okresowe aktualizacji  po zmianie kosztu łącz 4-13 13 Algorytm rutingu stanu łącza (SŁ) Notacja:  topologia sieci, koszty łącz znane  A: źródło wszystkim węzłom  c(i,j): koszt łącza z węzła i Algorytm Dijkstry do j. Koszt jest nieskończony, gdy węzły nie stanu łącza” są bezpośrednimi sąsiadami  wszystkie węzły mają tę samą  D(v): aktualna wartość informację kosztu ścieżki od źródła do  oblicza ścieżki najmniejszego celu v kosztu od jednego węzła  p(v): węzeł poprzedzający (‘źródła”) do wszystkich v na ścieżce od źródła do v pozostałych węzłów  N: zbiór węzłów, do  zwraca tablicę rutingu dla których najtańsze ścieżki źródła są na pewno znane  iteracyjny: po k iteracjach, zna najtańsze ścieżki do k celów  osiągane przez “rozgłaszanie 4-14 14 7 Algorytm Dijsktry 1 Inicjalizacja: 2 N = {A} 3 dla wszystkich węzłów v 4 if v sąsiaduje z A 5 then D(v) = c(A,v) 6 else D(v) = nieskończoność 7 8 Loop 9 znajdź w nie będące w N takie, że D(w) jest najmniejsze 10 dodaj w do N 11 aktualizuj D(v) dla wszystkich v sąsiednich do w i nie w N: 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 15 aż wszystkie węzły będą w N 4-15 15 Algorytm Dijkstry: przykład Krok 0 1 2 3 4 5 zbiór N A AD ADE ADEB ADEBC ADEBCF D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F) 2,A 1,A 5,A nieskończ. nieskończ. nieskończ. 2,A 4,D 2,D 4,E 2,A 3,E 4,E 3,E 4,E 5 2 A B 2 1 D 3 C 3 1 5 F 1 E 2 4-16 16 8 Algorytm Dijkstry: dyskusja Złożoność algorytmu: dla n węzłów  każda iteracja: musi sprawdzić wszystkie węzły w, które nie są w N  n(n+1)/2 porównań: O(n2)  bardziej wydajne implementacje możliwe: O(nlogn) Możliwe są oscylacje:  n.p., koszt łącza = ilość ruchu na łączu D 1 1 0 A 0 0 C 1+e e e B 1 początkowo 2+e A 0 0 D 1+e 1 B 0 0 C D … policz ponownie ruting A 2+e B 2+e A 0 1+e D 1+e 1 B e 0 C … policz ponownie … policz ponownie 4-17 1 0 0 C 17 Algorytm rutingu wektora odległości (WO) iteracyjny:  alg. działa, dopóki węzły wymieniają informacje.  automatyczne zakończenie: nie ma “sygnału” stopu asynchroniczny:  węzły nie wymieniają informacji jednocześnie! rozproszony:  każdy węzeł porozumiewa się tylko z bezpośrednimi sąsiadami Struktura danych "wektor odległości"  każdy węzeł ma swoją  jeden wiersz dla każdego celu  kolumna dla każdego bezpośredniego sąsiada węzła  przykład: w węźle X, dla celu Y przez sąsiada Z: X D (Y,Z) odległość od X do = Y, przez Z jako nast. krok Z = c(X,Z) + minw{D (Y,w)} 4-18 18 9 Wektor odległości: przykład 7 B A 1 E 2 A B D A 1 14 5 D B 7 8 5 D C 6 9 4 D 4 11 2 D E D (C,D) = c(E,D) + minw {D (C,w)} = 2+2 = 4 E D (A,D) = c(E,D) + minw {D (A,w)} = 2+3 = 5 pętla! E koszt do celu przez E D () 2 8 1 C B D (A,B) = c(E,B) + minw{D (A,w)} = 8+6 = 14 pętla! 4-19 19 Tablica odległości daje tablicę rutingu koszt do celu przez E Następne łącze na ścieżce do celu, koszt łącza D () A B D A 1 14 5 A A,1 B 7 8 5 B D,5 C 6 9 4 C D,4 D 4 11 2 D D,2 Tablica odległości Tablica rutingu 4-20 20 10 Ruting wektora odległości: przegląd Iteracyjny, asynchroniczny: Każdy węzeł: każda lokalna iteracja powodowana przez:  lokalną zmianę kosztów łącz  komunikat od sąsiada: zmiana najlepszej ścieżki od sąsiada do innego węzła Rozproszony:  każdy węzeł zawiadamia tylko sąsiadów jeśli jego najlepsza ścieżka do innego węzła zmieni się  następnie sąsiedzi zawiadamiają swoich sąsiadów, jeśli trzeba czeka na (zmianę kosztu lokalnych łącz lub komunikat od sąsiada) oblicza nową tablicę odległości jeśli najlepsza ścieżka do innego węzła zmieniła się, zawiadamia sąsiadów 4-21 21 Algorytm wektora odległości: W każdym węźle X: 1 Inicjalizacja: 2 Dla wszystkich sąsiednich węzłów v: 3 D X(*,v) = nieskończoność // operator * oznacza "dla wszystkich wierszy" X 4 D (v,v) = c(X,v) 5 dla wszystkich celów, y X 6 wyślij min D (y,w) do każdego węzła // w to kolejni sąsiedzi X w 4-22 22 11 Algorytm wektora odległości (c.d.): 8 loop 9 wait (dopóki koszt łącza do sąsiada V nie zmieni się 10 or dopóki nie otrzymam komunikatu od sąsiada V) 11 12 if (c(X,V) zmieniło się o d) 13 14 15 dla wszystkich celów y: DX(y,V) = D X(y,V) + d 16 17 else if (komunikat od V o celu Y) 18 19 20 21 dla jednego celu y: DX(Y,V) = c(X,V) + nowaWar 22 23 if jeśli mamy nowe min w DX (Y,w) dla dowolnego celu Y 24 wysyłam nową wartość min w DX (Y,w) do wszystkich sąsiadów 25 4-23 26 forever 23 Algorytm wektora odległości: przykład koszt przez koszt przez cel cel Z cel 7 1 cel cel cel X Y koszt przez koszt przez koszt przez 2 koszt przez koszt przez koszt przez koszt przez cel cel cel 4-24 24 12 Algorytm wektora odległości: przykład koszt przez koszt przez cel cel 2 X Y 1 7 Z koszt przez Z X D (Y,Z) = c(X,Z) + minw{D (Y,w)} = 7+1 = 8 cel Y X D (Z,Y) = c(X,Y) + minw {D (Z,w)} = 2+1 = 3 koszt przez cel 4-25 25 Wektor odległości: zmiany kosztów łącz Zmiany kosztów łącz:  węzeł wykrywa lokalną zmianę kosztów łącz  aktualizuje tablicę odległości (linia 15)  jeśli koszt najlepszej ścieżki się zmienił, zawiadamia sąsiadów (linie 23,24) koszt przez “dobre wieści szybko się rozchodzą” 1 4 X Y 50 1 Z koniec algorytmu koszt przez czas zmiana c(X,Y) 4-26 26 13 Wektor odległości: zmiany kosztów łącz Zmiany kosztów odległości:  dobre wieści szybko się rozchodzą... ...a złe wieści, powoli – problem “odliczania w nieskończoność”! Dlaczego tu jest 6??? 60 Y 4 X 1 Z 50 koszt przez algorytm dalej działa! koszt przez czas zmiana c(X,Y) 4-27 27 Wektor odległości: zatruty powrót Jeśli Z rutuje przez Y do X :  Z powie Y, że odległość (z Z) do X jest nieskończona (żeby Y nie rutował do X przez Z)  czy to całkiem rozwiązuje problem odliczania w nieskończoność? koszt przez 60 4 X Y 50 1 Z koniec algorytmu koszt przez czas zmiana c(X,Y) 4-28 28 14 Porównanie algorytmów SŁ i WO Odporność: co się stanie w razie awarii rutera?  SŁ: dla n węzłów, E łączy, O(nE) komunikatów SŁ: Złożoność komunikacji  WO: komunikacja tylko pomiędzy sąsiadami  czas zbieżności jest zmienny Szybkość zbieżności  SŁ: O(n2)  może mieć oscylacje  WO: czas zbieżności zmienny  mogą wystąpić pętle  problem odliczania w  węzeł może rozgłosić nieprawdziwy koszt łącza  każdy węzeł oblicza tylko swoją tablicę WO:  węzeł może rozgłosić nieprawdziwy koszt ścieżki  tabela każdego węzła jest używana przez inne nieskończoność błędy propagują się przez sieć 4-29 29 Plan całości wykładu  Wprowadzenie  Warstwa aplikacji  Warstwa transportu  Warstwa sieci  Warstwa łącza i sieci lokalne  Podstawy ochrony informacji (2 wykłady) (2 wykłady) (2-3 wykłady) (2-3 wykłady) (3 wykłady) (2-3 wykłady) 4-30 30 15 Mapa wykładu  4.1 Usługi warstwy sieci z komutacją pakietów  4.2 Zasady działania rutingu  4.3 Ruting hierarchiczny  4.4 Protokół Internetu (IP)  4.5 Ruting w Internecie  4.6 Co jest w ruterze  4.7 IPv6  4.8 Ruting rozsiewczy (multicast)  4.9 Mobilność 4-31 31 Przegląd architektury rutera Dwie główne funkcje rutera:  algorytm rutingu (RIP, OSPF, BGP)  przekazywanie pakietów z łącz wejściowych na wyjściowe port wejściowy port wyjściowy pole komutacyjne port wejściowy port wyjściowy procesor rutera 4-32 32 16 Funkcje portu wejściowego zakończenie linii Warstwa fizyczna odbiór sygnałów Warstwa łącza: n.p., Ethernet (patrz nast. część wykładu) obsługa warstwy łącza (dekapsulacja) kierowanie ruchu kolejka pole komutacyjne Zdecentralizowane przełączanie:  znając odbiorcę pakietu, znajdź port wyjściowy używając tablicy rutingu w pamięci portu wejściowego  cel: zakończyć obsługę w porcie wejściowym ‘z szybkością łącza’  kolejkowanie: jeśli pakiety przybywają szybciej niż szybkość przekazywania do pola komutacyjnego 4-33 33 Kolejkowanie w portach wejściowych  Gdy pole komutacyjne wolniejsze niż połączony ruch z portów wejściowych -> mogą się pojawić kolejki w portach wejściowych  blokowanie w kolejce: pakiet z przodu kolejki może uniemożliwić przekazanie dalej pakietów za nim  opóźnienie i straty spowodowane przez przepełnienie buforów portów wejściowych! pole komutacyjne pole komutacyjne konkurencja o porty wyjściowe: tylko jeden czerwony pakiet może zostać wysłany na raz zielony pakiet jest zablokowany w kolejce 4-34 34 17 Trzy rodzaje pól komutacyjnych pamięć szyna pamięciowe krata 4-35 35 Przełączanie w pamięci Pierwsza generacja ruterów:  pakiet kopiowany przez (pojedynczy) procesor rutera  prędkość ograniczona przez przepustowość pamięci (2 przejścia przez magistralę dla każdego pakietu) Port wejściowy Pamięć Port wyjściowy Magistrala systemowa Nowoczesne rutery:  procesor portu wejściowego zagląda do tablic rutingu, kopiuje pakiet do pamięci  Cisco Catalyst 8500 4-36 36 18 Przełączanie za pomocą szyny  pakiet przesyłany z pamięci portu szyna wejściowego do pamięci portu wyjściowego przez wspólną szynę  konkurencja o szynę: szybkość ograniczona przez przepustowość szyny  szyna 1 Gb/s, Cisco 1900: dostatecznie szybka dla ruterów dostępowych i ruterów małych organizacji (ale nie dla ruterów regionalnych i szkieletowych) 4-37 37 Przełączanie za pomocą kraty  przezwycięża ograniczenie przepustowości szyny  sieci firmy Banyan (VINES), inne sieci połączeń zaprojektowane początkowo do łączenia procesorów w superkomputerach  Zaawansowana technologia: podział pakietu na komórki ustalonej wielkości, przełączanie komórek przez kratę.  Cisco 12000: przełącza z szybkością Gb/s przez kratę 4-38 38 19 Porty wyjściowe pole komutacyjne kolejka, zarz. kolejnością obsługa warstwy łącza (enkapsulacja) zakończenie linii  Kolejkowanie jest potrzebne, gdy pakiety przybywają z pola komutacyjnego szybciej, niż prędkość transmisji łącza  Zarządzanie kolejnością wybiera pakiety z kolejki do transmisji 4-39 39 Mapa wykładu  4.1 Usługi warstwy sieci z komutacją pakietów  4.2 Zasady działania rutingu  4.3 Ruting hierarchiczny  4.4 Protokół Internetu (IP)  4.5 Ruting w Internecie  4.6 Co jest w ruterze  4.7 IPv6  4.8 Ruting rozsiewczy (multicast)  4.9 Mobilność 4-41 41 20 Ruting hierarchiczny Dotychczas w dyskusji rutingu robiliśmy upraszczające założenia  wszystkie rutery są identyczne  sieć jest “płaska” … które nie są prawdziwe w praktyce skala: przy 200 milionach celów: autonomia administracyjna wszystkich celów w tablicach rutingu!  wymiana tablic rutingu zalała by sieć!  każdy administrator sieci  nie można przechowywać  internet = sieć sieci może chcieć kontrolować ruting w swojej sieci 4-42 42 Ruting hierarchiczny  łączy rutery w regiony, tak zwane systemy autonomiczne (ang. “autonomous systems”, AS)  rutery w tym samym AS używają tego samego protokołu rutingu  protokół “wewnętrzny” systemu autonomicznego  rutery w różnych AS mogą używać różnych protokołów rutingu wewnętrznego rutery-bramy  specjalne rutery w AS  tak jak wszystkie rutery w AS, używają rutingu wewnętrznego  są także odpowiedzialne za ruting do celów z poza AS  używają protokołu rutingu zewnętrznego z innymi ruteramibramami 4-43 43 21 Ruting wewnętrzny i zewnętrzny C.b a C Bramy: B.a A.a b A.c d A a a pomiędzy sobą wykonują ruting zewnętrzny z innymi ruterami w swoim AS wykonują ruting wewnętrzny c b B c b ruting zewnętrzny, wewnętrzny w bramie A.c ruting wewnętrzny warstwa sieci ruting zewnętrzny warstwa łącza warstwa fizyczna 4-44 44 Ruting wewnętrzny i zewnętrzny Ruting zewnętrzny pomiędzy AiB B.a C.b a Host h1 C b A.a A.c a d c b A Ruting wewnętrzny w AS A a Host h2 c B b Ruting wewnętrzny w AS B  Niedługo poznamy protokoły rutingu wewnętrznego i zewnętrznego w Internecie 4-45 45 22 Warstwa transportu 3-1 Mapa wykładu  Usługi warstwy transportu  Multipleksacja i demultipleksacja  Transport bezpołączeniowy: UDP  Zasady niezawodnej komunikacji danych  Transport połączeniowy: TCP  struktura segmentu  niezawodna komunikacja  kontrola przepływu  zarządzanie połączeniem  Mechanizmy kontroli przeciążenia  Kontrola przeciążenia w TCP 3-2 1 Usługi i protokoły warstwy transportu  logiczna komunikacja pomiędzy procesami aplikacji działającymi application transport na różnych hostach network link  protokoły transportowe działają data physical na systemach końcowych  nadawca: dzieli komunikat aplikacji na segmenty, przekazuje segmenty do warstwy sieci  odbiorca: łączy segmenty w komunikat, który przekazuje do warstwy aplikacji  więcej niż jeden protokół transportowy  Internet: TCP oraz UDP ale może też być SAP (NetWare) network data link physical network data link physical network data link physical network data link physical network data link physical application transport network data link physical 3-3 Warstwy transportu i sieci  warstwa sieci: logiczna Analogia:  warstwa transportu:  procesy = pracownicy komunikacja pomiędzy hostami logiczna komunikacja pomiędzy procesami  korzysta z oraz uzupełnia usługi warstwy sieci pracownicy firmy zamawiają pizzę  komunikaty = pizze  hosty = firma i pizzeria  protokół transportowy = zamawiający pracownik  protokół sieci = doręczyciel pizzy 3-4 2 Protokoły transportowe Internetu  niezawodna, uporządkowana komunikacja (TCP) application transport network data link physical  kontrola przeciążenia  kontrola przepływu  tworzenie połączenia  zawodna, nieuporządkowana komunikacja (UDP) network data link physical network data link physical network data link physical network data link physical network data link physical  proste rozszerzenie usługi “best-effort” IP application transport network data link physical  niedostępne usługi:  gwarancje maksymalnego opóźnienia  gwarancje minimalnej przepustowości 3-5 Mapa wykładu  Usługi warstwy transportu  Multipleksacja i demultipleksacja  Transport bezpołączeniowy: UDP  Zasady niezawodnej komunikacji danych  Transport połączeniowy: TCP  struktura segmentu  niezawodna komunikacja  kontrola przepływu  zarządzanie połączeniem  Mechanizmy kontroli przeciążenia  Kontrola przeciążenia w TCP 3-6 3 Multipleksacja/demultipleksacja Multipleksacja u nadawcy zbieranie danych z wielu gniazd, dodanie nagłówka (używanego później przy demultipleksacji) Demultipleksacja u odbiorcy przekazywanie otrzymanych segmentów do właściwych gniazd = gniazdo = proces aplikacji P3 P1 P1 aplikacji P4 P2 aplikacji transportu transportu transportu sieci sieci sieci łącza łącza łącza fizyczna fizyczna host 1 host 2 fizyczna host 3 3-7 Jak działa demultipleksacja  host otrzymuje pakiety IP  każdy pakiet ma adres IP nadawcy, adres IP odbiorcy  każdy pakiet zawiera jeden segment warstwy transportu  każdy segment ma port nadawcy i odbiorcy (pamiętać: powszechnie znane numery portów dla określonych aplikacji)  host używa adresu IP i portu żeby skierować segment do odpowiedniego gniazda 32 bity port nadawcy port odbiorcy inne pola nagłówka dane aplikacji (komunikat) format segmentu TCP/UDP 3-8 4 Demultipleksacja bezpołączeniowa  Gniazda są tworzone przez podanie numeru portu: DatagramSocket mojeGniazdo1 = new DatagramSocket(99111); DatagramSocket mojeGniazdo2 = new DatagramSocket(99222);  Gniazdo UDP jest  Kiedy host otrzymuje segment UDP:  sprawdza port odbiorcy w segmencie  kieruje segment UDP do gniazda z odpowiednim numerem portu identyfikowane przez parę:  Datagramy IP z różnymi adresami IP lub (adres IP odbiorcy, port odbiorcy) portami nadawcy są kierowane do tego samego gniazda 3-9 Demultipleksacja bezpołączeniowa (c.d.) DatagramSocket gniazdoSerwera = new DatagramSocket(6428); P2 PN: 6428 PO: 9157 klient IP: A P1 P1 P3 PN: 9157 PO: 6428 PN: 6428 PO: 5775 serwer IP: C PN: 5775 PO: 6428 klient IP:B Port nadawcy (PN) jest „adresem zwrotnym”. 310 5 Demultipleksacja połączeniowa  Gniazdo TCP jest określane  Host serwera może przez cztery wartości:  adres IP nadawcy obsługiwać wiele gniazd TCP jednocześnie:  port nadawcy  każde gniazdo ma inne 4 wartości  adres IP odbiorcy  Serwery WWW mają  port odbiorcy  Host odbierający używa wszystkich 4 wartości, żeby skierować segment do właściwego gniazda  Uwaga: host sprawdza także 5 wartość: protokół oddzielne gniazda dla każdego klienta  HTTP z nietrwałymi połączeniami wymaga oddzielnego gniazda dla każdego żądania 311 Demultipleksacja połączeniowa (c.d) P1 P4 P5 P2 P6 P1P3 PN: 5775 PO: 80 IP-N: B IP-O: C klient IP: A PN: 9157 PO: 80 IP-N: A IP-O: C serwer IP: C PN: 9157 PO: 80 IP-N: B IP-O: C klient IP: B 312 6 Demultipleksacja połączeniowa i serwer wielowątkowy P1 P2 P4 P1P3 PN: 5775 PO: 80 IP-N: B IP-O:C klient IP: A PN: 9157 PO: 80 IP-N: A IP-O: C serwer IP: C PN: 9157 PO: 80 IP-N: B IP-O: C klient IP: B 313 Porty komunikacyjne  Numer przydzielony przez system: 0  po wywołaniu bind system wybiera numer portu 10245000 (znaleźć go można po wywołaniu getsockname())  Porty zarezerwowane: 1-1023  Porty dobrze znane: 1-255 (/etc/services)  Porty zwyczajowo zarezerwowane dla Unixa BSD: 256511  Przydzielane przez rresvport: 512-1023  Porty wolne 1024-65535 314 7 Mapa wykładu  Usługi warstwy transportu  Multipleksacja i demultipleksacja  Transport bezpołączeniowy: UDP  Zasady niezawodnej komunikacji danych  Transport połączeniowy: TCP  struktura segmentu  niezawodna komunikacja  kontrola przepływu  zarządzanie połączeniem  Mechanizmy kontroli przeciążenia  Kontrola przeciążenia w TCP 315 UDP: User Datagram Protocol [RFC 768]  “bez bajerów”, “odchudzony” protokół transportowy Internetu  usługa typu “best effort”, segmenty UDP mogą zostać:  zgubione  dostarczone do aplikacji w zmienionej kolejności  bezpołączeniowy:  nie ma inicjalizacji między nadawcą i odbiorcą UDP  każdy segment UDP jest obsługiwany niezależnie od innych Czemu istnieje UDP?  nie ma inicjalizacji połączenia (co może zwiększać opóźnienie)  prosty: nie ma stanu połączenia u nadawcy ani odbiorcy  mały nagłówek segmentu  nie ma kontroli przeciążenia: UDP może słać dane tak szybko, jak chce 316 8 Więcej o UDP  Często używane do Długość segmentu UDP w bajtach (z nagłówkiem) komunikacji strumieniowej  tolerującej straty  wrażliwej na opóźnienia 32 bity port nadawcy port odbiorcy długość suma kontrolna  Inne zastosowania UDP  DNS  SNMP  niezawodna komunikacja po UDP: dodać niezawodność w warstwie aplikacji  Praca domowa Dane aplikacji (komunikat) Format segmentu UDP 317 Suma kontrolna UDP Cel: odkrycie „błędów” (n.p., odwróconych bitów) w przesłanym segmencie Nadawca:  traktuje zawartość segmentu jako ciąg 16bitowych liczb całkowitych  suma kontrolna: dodawanie (i potem negacja sumy) zawartości segmentu  nadawca wpisuje wartość sumy kontrolnej do odpowiedniego pola nagłówka UDP Odbiorca:  oblicza sumę kontrolną odebranego segmentu  sprawdza, czy obliczona suma kontrolna jest równa tej, która jest w nagłówku:  NIE – wykryto błąd  TAK – Nie wykryto błędu. Ale może błąd jest i tak? Wrócimy do tego …. 318 9 Przykład sumy kontrolnej  Uwaga  Dodając liczby, reszta z dodawania najbardziej znaczących bitów musi zostać dodana do wyniku (zawinięta, przeniesiona na początek)  Przykład: suma kontrolna dwóch liczb 16-bitowych 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 zawinięcie 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 suma suma kontrolna 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 319 … na chwilę wracamy do Warstwy aplikacji 320 10 Mapa wykładu  2.1 Zasady budowy protokołów w. aplikacji  2.2 WWW i HTTP  2.3 DNS  2.4 Programowanie przy użyciu gniazd TCP  2.5 Programowanie przy użyciu gniazd UDP  2.6 Poczta elektroniczna  SMTP, POP3, IMAP  2.7 FTP  2.8 Dystrybucja zawartości  Schowki Internetowe  Sieci dystrybucji zawartości  2.9 Dzielenie plików P2P 21 Programowanie gniazd UDP UDP: brak “połączenia” pomiędzy klientem i serwerem  brak inicjalizacji połączenia  nadawca nadaje każdemu pakietowi adres IP i port odbiorcy  serwer musi pobrać adres IP, port nadawcy z otrzymanego pakietu punkt widzenia programisty UDP udostępnia zawodną komunikację ciągów bajtów (“datagramów”) pomiędzy klientem i serwerem UDP: wysyłane informacje mogą być gubione lub otrzymywane w innym porządku 22 11 Interakcja klient/serwer: UDP Serwer (działa na hostid) Klient tworzy gniazdo, port=x, dla nadchodzących połączeń : serverSocket = DatagramSocket(x) tworzy gniazdo, clientSocket = DatagramSocket() Tworzy, adresuje (hostid, port=x), wysyła datagram z komunikatem przez clientSocket czyta komunikat z serverSocket wysyła odpowiedź serverSocket podając adres i port klienta czyta odpowiedź z clientSocket zamyka clientSocket 23 Przykład: Klient w Javie (UDP) strumien wejsciowy Proces klienta monitor inFromUser klawiatura Wejście: odbiera pakiet (przez TCP odbierał “strumień bajtów”) pakiet UDP receivePacket pakiet (przez TCP, wysyłał “strumień bajtów”) sendPacket Wyjście: wysyła pakiet UDP gniazdo UDP clientSocket gniazdo klienta UDP do sieci z sieci 24 12 Przykład: klient w Javie (UDP) import java.io.*; import java.net.*; Tworzy strumień wejściowy class UDPClient { public static void main(String args[]) throws Exception { BufferedReader inFromUser = new BufferedReader(new InputStreamReader(System.in)); Tworzy gniazdo klienta DatagramSocket clientSocket = new DatagramSocket(); Tłumaczy nazwę na adres IP używając DNS InetAddress IPAddress = InetAddress.getByName("hostname"); byte[] sendData = new byte; byte[] receiveData = new byte; String sentence = inFromUser.readLine(); sendData = sentence.getBytes(); 25 Przykład: klient w Javie (UDP), c.d. Tworzy datagram z danymi do wysłania, długością, adresem IP, portem Wysyła datagram do serwera Czyta datagram z serwera DatagramPacket sendPacket = new DatagramPacket(sendData, sendData.length, IPAddress, 9876); clientSocket.send(sendPacket); DatagramPacket receivePacket = new DatagramPacket(receiveData, r