wide91.dvi

Size: px

Start display at page:

Download "wide91.dvi"

ともなりはらしない
5 years ago
Views:

1 6 183

3 1 IP n ( ) 1 ( ) Ethernet 48 MAC IP 32 IP IP ( )

4 WIDE (n ) 1 1 n 1 1 n n 1 n ( ) 1 n ( ) TCP/IP n 1 1 TCP/IP WIDE TCP/IP IP

5 2 IP IP 2.1 LAN DVMRP(Distance Vector Multicast Routing Protocol) RFC1075 [?], [?] Distance{Vector Routing Distance{Vector routing XNS routed gated UNIX [?] Distance{Vector routing (V;D) V D (1 ) ( ) 2 i 1 i 2 d(i 1 ;i 2 ) i j D(i; j) i k D(i; i) = 0 all i D(i; j) = min k [d(i; k)+d(k; j)] otherwise 187

6 WIDE Distance{Vector routing tree tree 2 single{spanning{tree single{ spanning{tree routing reverse path broadcast shortest{path broadcast tree shortest{path multicast tree LAN single{spanning{tree reverse path broadcast shortest 0 path multicasttree shortest 0 path broadcasttree shortest{path broadcast tree broadcast tree shortest{path multicast tree reverse path broadcast algorithm 4 Reverse Path Flooding (RPF) Revese Path Broadcasting (RPB) Truncated Reverse Path Broadcasting (TRPB) Reverse Path Multicasting (RPM) 4 RPF 0! RPB 0! TRPB 0! RPM 2

7 6 189 shortest{path broadcast tree LAN (RPF,RPB) shortest{path broadcast tree tree (TRPB,RPM) RPF shortest{path broadcast tree reverse path broadcast algorithm reverse path broadcast algorithm reverse path shortest{path (shortest{reverse{path) shortest{reverse{path Distance Vector broadcast tree LAN LAN 1 LAN LAN 2.1 c RPB RPF RPB 1 LAN 1

8 WIDE f s 4 5 g x y g a le0 b z w c le1 le0 u v e le1 d 2.1: LAN RPB 1 LAN 1 child link RPF child link child link child link parent router child link Distance Vector child link

9 6 191 child link children child link 2.1 z : RPB z destination distance next-gateway interface age children a c a 0 z le b 1 w le c 0 z le d 1 v le e 1 u le f 5 x le RPF children shortest{path broadcast tree RPF broadcast tree TRPB TRPB shortest{path broadcast tree ( ) (leaf link) 1 shortest{path broadcast tree shortest{path broadcast tree RPB 2

10 WIDE shortest{path broadcast tree (leaf link) ( ) leaf link child link child link leaf link leaf link parent router (reverse{path) Distance Vector split horizon split horizon [?] leaf link leaf link RPB child link leaves RPB leaves 2.1 v 2.2 LAN parent router parent router shortest{path broadcast tree O( 2 ) broadcast tree

11 : TRPB v destination distance next-gateway interface age children leafs c d c d a 0 z le b 1 w le c 0 v le d 1 v le e 1 z le f 6 z le LAN LAN leaf link O( ) broadcast tree tree broadcast tree broadcast tree

12 WIDE RPM RPM shortest{path broadcst tree TRPB tree TRPB 1 child link leaf link TRPB NMR(Non{ Membership report) (one{hop{back router) ( 2.2 ) NMR child link NMR NMR one{hop{back router s s a a b b c d e c d e (a) b sends NMR to a (b) b doesn t send NMR to a 2.2: NMR 2 shortest{path broadcast tree child link NMR subtree tree NMR age NMR tree age T maxage NMR NMR age 0 NMR NMR NMR age

13 6 195 T maxage NMR (Non{Membership Report Cancellation) NMR NMR NMR NMR T maxage ( NMR ) NMR RPM NMR TRPB NMR T maxage 2 2 NMR shortest{path broadcast tree tree tree TRPB broadcast tree NMR ( ) NMR scalability NMR tree

14 WIDE RPF RPB s s a b a b c c e d e d 2.3: Distance Vector reverse path broadcast tree tree tree reverse path broadcast tree shortest path reverse path tree Distance Vector Link{State Routing Link{State Routing New Arpanet Shortest Path Frst Arpanet ISO ANSI

15 6 197 TRPB s RPM s a b a b c c e d e d 2.4: Link{State Routing ( ) tree tree (shortest path rst ) [?] tree shortest path tree shortest{path multicast routing O( )

16 WIDE 1 shortest{path multicast tree shortest{path multicast tree RPM shortest{path multicast tree (source, subtree, (group,link-ttls), (group,link-ttls),...) source subtree shortest{path spanning tree subtree group link{ttls TTL ( ) TTL (group; link 0 ttls) link{ttls TTL TTL (group; link 0 ttls) subtree (group; link 0 ttls) link{ttls shortest{path spanning tree (group; link 0 ttls) RPM multicast tree

17 6 199 shortest{path multicast tree RPM shortest{path single spanning tree tree ANSI Distance Vector Routing Link{State Routing shortest{ path multicast tree LAN LAN LAN [?]

18 WIDE 2.2 IP 1 TCP/IP IP IP 1 Class A network host Class B 1 0 network host Class C network host Class D multicast address 2.5: IP IP D D IP 4 \1110" (IP ) 1 IP, IP 1 VMTP

19 6 201 IP 2.3 TCP/IP TCP/IP 4 4 [?] 3 0 IP D IP IP 1 IP D IP IP 2 IP ( IGMP(Internet Group Management Protocol) ) ( ) 2 ( 2.6 )

20 WIDE ( ) IP IP ICMP IGMP (ARP) hardware 2.6: TCP/IP IP IP IP (TTL(time{to{live)) IP D IF D THEN ELSE ( )

21 6 203 IP 01:00:5E:00:00:00 23 IP 23 IP IP 2 point{to{point ARPANET X.25 store{and{forward IP IP IP IP IP IP IP 2 JoinHostGroup(group-address, interface) LeaveHostGroup(group-address, interface) interface IP 2 IP IP

22 WIDE IP ICMP(Internet Control Message Protocol) (IGMP[?]) IP IP 2 JoinLocalGroup(group-address) LeaveLocalGroup(group-address) IP IP point{to{point store{and{forward TCP/IP IP

23 6 205 IP header IGMP header DVMRP message 2.7: DVMRP 2.4 IP (DVMRP) RPM TRPB MUTICAST 1.2 Release mrouted [?] TCP/IP TRPB IP (2.3 ) 0! IP IP IP Distance Vector 0! DVMRP DVMRP IP IGMP DVMRP DVMRP DVMRP DVMRP IGMP [?] IGMP IP DVMRP 2.7 DVMRP 2.3 DA1 Metric Innity Flags0 Subnetmask 1

24 WIDE 2.3: DVMRP Value Name 0 Null Padding 2 AFI address family 3 Subnetmask subnet mask 4 Metric metric 5 Flags0 split horizon ag 6 Innity 7 DA destination address 8 RDA requested destination address 9 NMR non membership report 10 NMR-cancel non membership report cancel IP IP IP VERS HLEN SERVICE TYPE TOTAL LENGTH IDENTIFICATION FLAGS FRAGMENT OFFSET TIME TO LIVE PROTOCOL HEADER CHECKSUM SOURCE IP ADDRESS DESTINATION IP ADDRESS IP OPTIONS(IF ANY) PADDING DATA : IP IP ( 2.8) loose source route ( 2.8) loose source route IP

25 CODE(137) LENGTH POINTER IP ADDRESS OF FIRST HOP IP ADDRESS OF SECOND HOP : IP loose source route \loose" source route IP IP ( IP ) 1. 2 loose source route IP 2. source route pointer source route 2 ( 2.10(1)) 3. source route 1 ( 2.10(2)) 4. source route 2 ( 2.10(3)) 5. ( 2.10(4)) 6. ( 2.10(5)) ICMP loose source route

26 WIDE Original IP Multicast Datagram other IP header source IP address destination IP address data IP multicast Datagram for Tunneling other IP header v code length 88 (4) (5) 8 8 (2) (3) source IP address destination IP address (1) IP address of rst hop IP address of second hop data 2.10:

27 loose source route 1 2. loose source route 2 3. loose source route loose source route loose source route loose source route DVMRP Distance Vector RIP[?] RIP DVMRP DVMRP TRPB child link leaf link ( ) child (child link) leaf (leaf link) (child link ) (leaf link )

28 WIDE DVMRP DVMRP (TTL) 1 DVMRP DVMRP leaf link poisoned split horizon TRPB X X IF THEN destination address IF THEN IF THEN

29 6 211 IF THEN IF THEN IF THEN IF THEN IF THEN EXPIRATION TIMEOUT IF THEN min( ) ELSE ( ) IF ( EXPIRATION TIMEOUT ) THEN IP DVMRP TRPB IP child link leaf link child link leaf link IF IP TTL 2

30 WIDE THEN IP IF THEN IF next 0 hopvirtualinterface THEN IF tunnel THEN tunneling loosesourceroute IP IF 224:0:0:0 224:0:0:1 THEN FOR V IF V source childlist THEN IF V leaf leaf V THEN IF TTL V THEN TTL 1 V DVMRP TRPB Distance Vector DVMRP DVMRP IP IP IP 1 ICMP Router Discovery Messages RFC [?] IP DVMRP

31 DVMRP Distance Vector IP DVMRP point{to{point store{and{forward DVMRP IP reverse{path{algorithm reverse path

32 3 WIDE IP WIDE IP 3.1 IP FTP 1 IP TCP/IP B 3.2 LAN 10Mbps 214

33 6 215 Kbps scalability( ) scalability LAN point{to{point LAN point{to{point LAN LAN scalability ( )

34 WIDE 3.3 Reverse{Path Forwarding TRPB tree TRPB tree tree tree tree tree reverse{path ( ) scalability

35 LAN tree tree tree tree tree tree RTT(Round Trip Time) RTT

36 WIDE RTT 3.5 DVMRP 3.5.1

37 6 219 leaf link child link parent router DVMRP child link child link paret router leaf link parent router next hop router leaf link local group membership local group membership

38 WIDE ( ) (reverse path ) ( )

39 6 221 ( ) (1) (2) IF THEN IF ( ) ( 1 ) THEN ELSE 1

40 WIDE 1 2 DVMRP DVMRP DVMRP DVMRP 3.7 IP LAN tree

41 DVMRP DVMRP 1 Link{State Routing tree tree tree tree tree DVMRP Link{State Routing LAN LAN ( ) ( )

42 WIDE 3 satellite receiver satellite sender sender : ( )

43 6 225 ( ) ( ) 3.10 IP WIDE ( { ) { {

44 WIDE IP IP

45 6 227 point{to{point point{to{point B C C B B B 1 B point{to{point 2 point{to{point ( 3.2 ) IP IP IP 1 IP 1 point{ to-point

46 WIDE low spped network high spped network 3.2: 1 IP

47 6 229 { { IP IP 1{ (2.3.1 ) DVMRP [?] 128

48 WIDE 2{IP IP 3 IP IP 32 4 IP 4 28 IP IP IP 23 IP IP IP IP

49 6 231 IP ( 3.3 )

50 WIDE satellite sender satellite receiver sender 3.3: ( DVMRP (2.4.2 ) IP IP ) 2 (1) (2) (1) D 2 1 D IP

51 IP IP D (2) ((1) ) IP IF THEN ELSE (IP ) ( 3.4 ) / 1.

52 WIDE satellite sender satellite receiver sender 3.4: / 2. / IF THEN / 1. / 2. 1

53 DVMRP Link{State Routing Link{State scalability 1 scalability [?] IP

54 WIDE IP IP ( ) IP IP (1 IP ) ( ) ( ) IP ( ) 1 (T member1 ;T member2 ; 111;T membern ) 3.12

55 Distance{Vector routing Link{State routing Link{State routing

56 WIDE ( ) O( ) O( P ( 3 ))

57 O( ) 3 ( tree) ( ) RPM Non{Membership report Distance{Vector routing tree Distance{Vector routing Link{State routing

58 WIDE tree O( single 0 spanningtree ) [ 2] [ 1] 4 [ 1] [ 2] [ 3] [ 1][ 2][ 3] [ 4] [ 4]

59 Link{State [ 1] [ 5] [ 6] 6 ( ) ( ) O( ) 1. 2.

60 WIDE 3. 3 [ 6] n (T member1 (1);T member1 (2); 111;T member1 (n) ) (LRU(Least Recently Used) ) 6 [ 2][ 6] [ 2] [ 6]

61 6 243 IP [ 1] [ 5] IP IP tree single{spanning tree single{spanning tree tree tree A B

62 WIDE 1 ( 1) 2 ( 2) 6 TTL 2 IP TTL TTL 2.3 IP IP 2.5 IP

63 : 1 : : 2: " b " " b " b Yes b - "b bb "" b" No? 3: 3.5:

64 WIDE 3 ( 3) single{spanning tree

65 scalability { { { { { { { ( )

66 WIDE 2 1 f 2:1 2:3 g + f 3:1 3:2 g :1 + 3: :5 + 3: :4 + 3:1 3 TCP/IP 1

67 TTL 2 3 single{spanning tree

68 WIDE LUNA{II 5 Mach 2.5 UNIX 4.3BSD{ tahoe TCP/IP * hitomaro buson (hitomaro) ( 2) shikibu 0 * hitomaro * 6 issa buson komachi? (not support multicast) *: mrouted 3.6: DVMRP mrouted 1 VMTP[?,?,?] 4.3 BSD Stanford Steve Deering [?,?] mrouted MULTICAST 1.2 Release

69 6 251 mrouted 2.3 TCP/IP ( ) LUNA{II LUNA{II IGMP( ) netinet/{igmp.c,igmp.h,igmp_var.h} DVMRP netinet/{ip_mroute.c,ip_mroute.h} netinet/if_ether.{c,h} netinet/in.{c,h} netinet/in_pcb.{c,h} netinet/in_proto.c netinet/in_var.h netient/ip_icmp.c netinet/ip_input.c netinet/ip_output.c netinet/ip_var.h netinet/raw_ip.c net/if.{c,h} net/if_loop.c net/if_sl.c net/raw_cb.{c,h} h/ioctl.h h/mbuf.h netinet/udp_usrreq.c LUNA{II luna2if/if_am.c LUNA{II 4.3BSD{tahoe ( ) 3.6 * shikibu,komachi issa

70 WIDE IP mrouted ( ) mrouted IP IP a) b) a) ( ) ipintr() IF (IP LSRR ) THEN IP IF THEN ip mforward() input b) ip output() (3:14:5 ) IF THEN IF TTL THEN IF THEN ELSE IF ( 1 ) THEN ip mforward() output a) b) ip mforward()

71 6 253 ip mforward() ip mforward() IF THEN IP IP (1 33 ) (mrtnd())(2 33 ) FOR IF (children ) (leaf ) THEN IF THEN tunnel send() ELSE phyint send() mrouted mrouted (PROMISC, ALLMULTI ) #/etc/route add group-address interface-address : #/etc/route add ( )

72 WIDE mrouted 3.6 * mrouted phyint (2.4.2 ) tunnel ( vif )phyint tunnel point{to{point phyint tunnel tunnel phyint metric ( ) threshold ( ) tunnel mrouted () phyint [disable] [metric <m>] [threshold <t>] tunnel <local-addr> <remote-addr> [metric <m>] [threshold <t>] tunnel metric 3 mrouted vif vif MULTICAST 1.2 Release mrouted DVMRP mrouted 2.4 DVMRP mrouted DVMRP split horizon 2 split horizon with poisoned reverse

73 : MULTICAST 1.2 Release mtest netstat ping rwhod DVMRP rwhod child link leaf link mrouted IP DVMRP 1 leaf timeouts vif vif ( ) leaf link

74 WIDE TTL 2 IP 2 ( ) { TTL { ( ) { { { (0) 1 (1) (2) (3) ( )

75 6 257 (4) ( mrouted phyint, tunnel) mrouted <0> <1> ( ) ( (2) ) <2> ( (2) ) <3> ( (3) ) mrouted vif phyint, tunnel mrouted (DVMRP) DVMRP mrouted mrouted TTL IP TTL socket TTL TTL 1 TTL (0 ) [?] 128

76 WIDE TTL TTL TTL 128 mrouted 200 #define WIDE_MULTI_TTL 200 mrouted ip mforward() ( (1 33 ) (2 33 ) ) IP mrouted 2 IP mrouted mrouted IP mrouted wide-tunnel <local-addr> <remote-addr> wide-tunnel

77 vif mrouted 1 vif vif uvif vifctl vif mrouted vif vif VIFF WIDE TUNNEL #define VIFF_WIDE_TUNNEL 0x2 /* */ struct vif { u_char v_flags; /* VIFF_WIDE_TUNNEL */ u_char v_threshold; struct in_addr v_lcl_addr; struct in_addr v_rmt_addr; struct ifnet *v_ifp; struct mbuf *v_lcl_groups; u_long v_cached_group; int v_cached_result; struct in_addr v_wide_rmt_addr; /* WIDE_TUNNEL */ }; struct uvif { u_short uv_flags; /* VIFF_WIDE_TUNNEL */ u_char uv_metric; u_char uv_threshold; u_long uv_lcl_addr; u_long uv_rmt_addr; u_long uv_wide_rmt_addr; /* WIDE_TUNNEL */ u_long uv_subnet; u_long uv_subnetmask; u_long uv_subnetbcast; char uv_name[ifnamsiz]; struct listaddr *uv_groups;

78 WIDE }; struct listaddr *uv_neighbors; struct vifctl { vifi_t vifc_vifi; /* VIFF_WIDE_TUNNEL */ u_char vifc_flags; u_char vifc_threshold; struct in_addr vifc_lcl_addr; struct in_addr vifc_rmt_addr; struct in_addr vifc_wide_rmt_addr; /* WIDE_TUNNEL */ }; tunnel send() 1 vif vif tunnel tunnel send() tunnel send() tunnel send() tunnel send() wide tunnel send() ip mforward() IF THEN IP IP (1 33 ) IF IP TTL == WIDE MULT I TTL THEN VIFF WIDE TUNNEL vif wide tunnel send() (mrtnd())(3:14: ) wide tunnel send() IP ip output()

79 6 261 ( ) 3 vif v wide rmt addr NULL VIFF WIDE TUNNEL v wide rmt addr NULL wide-tunnel * vif ip mforward() vif vif vif IP LSRR (IP ) ipintr() ip mforward() vif vif (1) 2 NULL (2) NULL (3) 2 NULL (1) (3) (2) vif

80 WIDE TTL TTL TTL TTL WIDE MULTI TTL - 15 ip mforward() IF THEN FOR vif IF vif THEN IF vif null TTL THEN BREAK ELSE BREAK IF THEN FOR vif IF null THEN BREAK IF THEN ( ) IP IP (3:14: ) ( )

81 6 263 vif vif phyint wide-tunnel phyint sat-send vif #define VIFF_WIDE_SAT_SEND 0x4 ip mforward() IF THEN IP IP (3:14: ) IF THEN VIFF WIDE SAT SEND (mrtnd())(3:14: ) ip mforward() ip mforward() IF THEN IP IP (3:14: ) IF IP TTL==WIDE MULTI TTL THEN VIFF WIDE TUNNEL vif IF NULL THEN wide tunnel send() ELSE VIFF WIDE SAT SEND (mrtnd())(3:14: )

82 WIDE sat-send hitomaro issa wide-tunnel (receive-only) buson wide-tunnel : mtest ( 3.1 ) 3.6 shikibu komachi netstat ( 3.1 ) mine@shikibu<~>[20]netstat -nia Name Mtu Network Address Ipkts Ierrs Opkts Oerrs Coll am lo mrouted 3.7 netstat

83 6 265 buson, hitomaro Groups buson -M Virtual Interface Table Vif Threshold Local-Address Remote-Address Groups wide-tunnel Multicast Routing Table Hash Origin-Subnet In-Vif Out-Vifs * * hitomaro mine@hitomaro</usr/src/vmtp-ip/netstat.bsd>[20]netstat -M Virtual Interface Table Vif Threshold Local-Address Remote-Address Groups wide-sat-send wide-tunnel receive-only Multicast Routing Table Hash Origin-Subnet In-Vif Out-Vifs * * ping ping ( 3.1 ) ping TTL komachi ping 3.6 issa issa shikibu komachi komachi TTL ping komachi( )

84 WIDE -t PING ( ): 56 data bytes 64 bytes from icmp_seq=0 time=0 ms 64 bytes from icmp_seq=1 time=0 ms 64 bytes from icmp_seq=2 time=0 ms 64 bytes from icmp_seq=3 time=0 ms 64 bytes from icmp_seq=4 time=0 ms ^C PING Statistics packets transmitted, 5 packets received, 0% packet loss round-trip (ms) min/avg/max = 0/0/0 TTL 200 shikibu( ) TTL 200 shikibu( )

85 4 IP TTL TTL TTL TTL TTL TTL

86 WIDE TTL (1 1 ) 1 n ( ) 1 1 (DVMRP) 1

87 ( { ) {

88 WIDE WNOC INS64 ASTEM OMRON SFC

89 6 271 OMRON ASTEM UEC Ichigaya WNOC-TOKYO WNOC-SFC U-TOKYO 4.1:

90 WIDE

tcp/ip.key

tcp/ip.key IP TCP IP ヘッダデータ部ヘッダデータ部ヘッダデータ部 Ethernet パケット Ethernet パケット Ethernet パケット IP(1) 0 8 16 24 31 () Version IHL () Time To Live () Identification () Type of Service ) Flags Protocol () Source Address IP) Destination