Special Topics EECS 498
Popular in Course
verified elite notetaker
CLS 1500 - 03
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
Popular in Engineering Computer Science
This 77 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 498 at University of Michigan taught by Staff in Fall. Since its upload, it has received 7 views. For similar materials see /class/231550/eecs-498-university-of-michigan in Engineering Computer Science at University of Michigan.
Reviews for Special Topics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/29/15
Group Membership Service EECS 498 Lecture Notes Farnam Jahanian Department of EECS University of Michigan httpwwweecsu m ichedulfarnam Reading List 0 Section 139 in Building Reliable and Secure Network Applications by Ken Birman 1997 optional 0 Tanenbaum Section 72 Group Membership Problem 0 Agreement on the membership of a group of cooperating processes in a distributed system 0 Consistent systemwide view of the operational members in the presence of processor or process failure processor or process join processor or process departures communication failure 0 Group Membership Service maintains membership of a distributed system on behalf of processes that compose it G MP Informal Definition 0 All operational members see the same sequence of view transitions 1 Linear order on system View changes 0 See Figure 1 0 Several research papers formally define the problem beyond the scope Figure 1 GM View Changes P1 I I I I 3 P1 joins P4joins P2 joins P3 joins p1 fails P2 lt I I P2 joins P3joins P3 I I P3 joins I P1 fails P4 1 I I I P4 joins P2 joins P3joins P1 fails P1 P1P4 P1P4P2 P1P4P2P3 P4P2P1 What is difficult about this problem Main Challenge in Asynchronous Systems It is difficult to distinguish between a process that has crashed and a process that is very slow Perceived failure of processors due to message loss or communication delay Timeouts it is impossible to determine with absolute certainty whether a processor has crashed in an asynchronous distributed system Related issues Initial system startup bootstrap problem Multiple concurrent failures Coordinator failurepartition handling Precise meaning of a consistent View Heartbeathardware multicast support Coordinatorbased Approach 0 Used in many group communication systems including ISIS Horus RTCAST Amoeba Unique identifier for each member eg lP addr processid Linear ordering of member ids o Designate a coordinator or manager for maintaining and disseminating membership information 0 Two cases member noncoordinator failure 2phase protocol coordinator failure 3phase protocol Case 1 Noncoordinator Failure failure v Q removeQ Com m itQ z V V Phase I Phase II Case 2 Coordinator Failure failure V 000 rd i nator X interrogation propose com in it Y z V V Phase I Phase II Phase III Coordinator Failure axe Heartbeat lt gt Partition Handling Primary partition group eg ISIS system majority partition continues membership of subsequent group should overlap with the membership of current group minority group suspends potential for singleton groups and lack of progress Allow partitions and remerge eg Transis system Allow nonoverlapping simultaneous groups Service Model Node 1 Node 2 Node 3 Membership Membership Membership Daemon Daemon Daemon EECS 498 Lecture Notes 1 b Introduction to Distributed Systems Farnam Jahanian Department of EECS University of Michigan EECS 498 Lecture Notes httpwwweecsumichedulfarnam Lectures Weeks 1 3 Introduction to Networking communication issues and network technologies Reading list Tanenbaum text Chapter 21 pp 5768 Layered Protocols Handout in class Chapter 5 Protocols Underlying HTTP from Web Protocols and Practices by Krishnamurthy amp Rexford 2001 Introduction to distributed systems characteristics of distributed systems design issues hs concepts distributed programming models Reading list Tanenbaum text Chapter 1 pp 142 Overview of Distributed Computing Paradigms Reading List Handout in class Chapter 3 from Distributed Computing Principles and Applications text by ML Liu recommended text Introduction to Distributed Systems Distributed Systems Three Technology Advances 0 Development of powerful microprocessors 0 Development of highspeed networks 0 Development of denser and cheaper memorystorage Easy put together large of powerful processors connected by a high speecl network Hard SOFTWARE SOFTWARE SOFTWARE Distributed Systems What is a distributed system You know you have one when the crash of a computer you ve never heard ofstops you from getting any work done Leslie Lamport A collection of perhaps heterogeneous nodes connected by one or more interconnection networks which provides access to systemwide shared resources and services A collection of independent computers that appears to its users as a single coherent system Examples Characteristics of a distributed systems Multiple Computers More than one physical computer each consisting of CPUs local memory and possibly stable storage and Ho paths to connect it with the environment Interconnections Mechanisms for communicating with other nodes via a network Shared State If a subset of nodes cooperate to provide a service a shared state is maintained by these nodes The shared state is distributed or replicated among the participants An Abstract View Distributed Systems Machine A Machine B Machine C Distributed applications Middleware service Local 08 Local 08 Local 08 Network A distributed system organized as middleware Note that the middleware layer extends over multiple machines Distributed vs Centralized Systems Why distribute Resource sharing Device sharing Flexibility to spread load Incremental growth Costperformance ReliabilityAvailability Inherent distribution Security Why NOT distribute Software Network Security System management Numerous sources of complexity including TransparentJuniform access to data or resources Independent failures of processors or processes Dynamic membership of a system Unreliableunsecured communication Overhead in message communication Distribution or replication of data or metadata Lack of clean common interfaces Design Goals amp Issues Connecting users and resources is the primary goal Transparency hide the fact that processes and resources are physically distributed Openness offer services according to rules and interfaces that describe the syntax and semantics of those services Interoperability and portability Separating policy from mechanism Scalability Performance Dependability Transparency in a Distributed System Tramparerlo Description Access Hide drrerences in data representation and how a resource is accessed Location Hide where a resource is located Mi gation Hde that a resouce may move to another location Relocation Hde that a resouce may be moved to another location while in use Replication Hde that a resouce may be shared by several competitive Lsers Concurrency Hde that a resouce may be shared by several competitive Lsers Failure Hde the failure and recovery ofa resource persistence Hide whether a so ware resource is in memory or on disk Different forms of transparency in a distributed system Transparency o How to achieve singlesystem image How to hide distribution from users or programs 0 Is it a good idea Sometimes requires trade off transparency for performance Scalability o The challenge is to build distributed systems that scale with the increase in the number of CPUs users and processes larger databases etc o Scalability along several dimensions size geography administrative domains Scalability Problems Concept Example Centralized services A single server for all users Examples of scalability limitations How to scale A very simple principle Avoid centralized services centralized tables and centralized algorithms Characteristics of decentralized algorithms No machine has complete information about the system state Machines make decisions based only on local information Failure of one machine does not ruin the algorithm There is no implicit assumption about a global clock A few lessons from AFS Clients have cycles to burn Cache whenever possible Exploit usage properties Minimize systemwide knowledgechange Batch if possible Multicast often works Scaling Techniques Tanenbaum s Text Hiding communication latencies oz Asynchronous communication oz Function shipping to clients Distribution of components oz DNS name space Caching and Replication oz Maintaining consistency Scaling Techniques 1 Client Server FIRST NAME LAsT NAME E MAI L VAN ST STEENCS VU NL EEN FIRS LAST NAM EMAIL T NAME E VAN ST STEENCS VU NL Check form Process form a Client Server MAARTEN VAN s 55 TEEN STEENCS VU NL V Check form Process form b a a server or b a client check forms as they are being lled Scaling Techniques 2 i4 Generic J L Countries mm org Jp QB nl w Wquot W K939 1quot Sun i en 25gt 39 ack jill n ai linda c robot An example of dividing the DNS name space into zones Performance Various performance metrics 0 response time throughput system utilization network capacity utilization Key issue in parallelizing computations in a distributed system overhead of message communication Pe ormance Trade off 0 More tasks 9 more parallelism 9 better performance 0 More tasks 9 more communication 9 worse performance Grain size affects of messages finegrained parallelism vs coarsegrained parallelism small computations large computations high interaction rate low interaction rate Dependab y Reliability measured by the probability Rt that the system is up and providing correct service during the time interval 0t assuming that it was operational at time t Availability measured by the probability At that the system is operational at the instant of time t As t 9 on availability expresses the fraction of time that the system is usable Timeliness ability to meet timing constraints imposed on task execution or service delivery lnteg rity replicated copies of data must be kept consistent Security protection from unauthorized usageaccess Why more difficult in distributed systems Distributed Programming Paradigms Clientserver model Remote procedure calls Distributed File Systems Group communication and multicasts Distributed transactions Distributed shared memory Distributed objectbased systems Publishsubscribe model Peertopeer model The Web Hardware Concepts Shared memory y E E E E E Processor E Memory Different bas1c organlzatlons and memorles 1n d1str1buted computer systems Private memory pesEqsng pesequoums 3 Multiprocessors 1 o A busbased multiprocessor CPU CPU CPU Memory Ca che Cache Cache Multiprocessors 2 a A crossbar switch b An omega switching network Memovles E W 11 CPUs WW i Crosspoml swash m swrich ta m Homogeneous Multicomputer Systems a Grid b Hypercube a b Heterogeneous Multicomputer Systems 0 Most distributed systems today are built on top of heterogeneous multicomputers and interconnection networks 0 No global system View 0 Sophisticated software needed to support distributed applications Software Concepts An overview of DOS Distributed Operating Systems NOS Network Operating Systems Middleware Uniprocessor Operating Systems 0 Separating applications from operating system code through a microkemel No dired data exchange between modules L w Process File moduie m dule E Kernel mode System can A quot Mmmkemei y OS mieriace Hamvmre Multiprocessor Operating Systems 1 monitor Counter private int count 0 public int value return count void incr count count 1 void decr count count 1 I A monitor to protect an integer against concurrent access Multiprocessor Operating Systems 2 monitor Counter private void decr int count 0 if count 0 int blockediprocs 0 blockediprocs blockediprocs 1 condition unblocked wait unblocked public blockediprocs blockediprocs 1 int value 0 return count void incr else if blockediprocs 0 count count 1 count count 1 else signal unblocked I A monitor to protect an integer against concurrent access but blocking a proc Multicomputer Operating Systems 1 0 General structure of a multicomputer operating system Machine A Machine B Machine C Distributed applications Distributed operating system services Kernel Kernel Kernel Network Multicomputer Operating Systems 2 I Alternatives for blocking and buffering in message passing Possible synchronization point Sender Receiver sender Receiver buf fer bU er Network Multicomputer Operating Systems 3 humn39nn Distributed Shared Memory Systems 1 a Pages of address space distribute among four machines Memry Situation after CPU 1 references page 10 E c Situation if page 10 is read only and Distributed Shared Memory Systems 2 False sharing of a page between two independent processes Machine A Page transfer when Machine B B needs to be accessed 3 A 1 Two independent 3 l l data items Page transfer when l quot A needs to be accessed l Page p Code using A Code using B Network Operating System 1 0 General structure of a network operating system Machine A Machine B Machine C Distributed applications I Network OS Network 08 Network 08 services services services Kernel Kernel Kernel Network Network Operating System 2 Two clients and a server in a network operating system File server Disks on which shared file system Client 1 is stored Request Reply Network Network Operating System 3 Different clients may mount the servers in different places Chem 1 Cum 2 Save 1 Serve 2 I gain as wark private pacmzn mall pamman teaching paecmld research 3 Chem 1 Chem 2 ringzmes r 7 privategames work 0 work i iri pacmau vnail pacman mail pamman teaching pacwoman teaching pacchlld research paccl39ul research 5 Positioning Middleware 0 General structure of a distributed system as middleware Machine A Machine B Machlne c l Distributed applications Middleware services Network 03 Network 08 Network 05 semoes services sewices Kernel Kernel I Kernel Network Middleware and Openness Application Same Application programming interface A Middleware Middleware Network 08 protocol Network 08 o In an open k A J L by each middleware layer should be the same as well as the interfaces they offer to applications EECS 498 Lecture Notes 4 Prof Farnam Jahanian UniV of Michigan The ClientServer Model 7 Section 15 Tanenbaum 7 Handout in class RPC Reliable RPC 7 Section 22 Tanenbaum 7 Section 73 Tanenbaum The ClientServer Model Key Idea Structure a distributed system as a collection or group of cooperating processes called servers that offer services to users called clients request gt lt reply Examples The ClientServer Model Wait for result Client Request Server 77777777777 W PrOVIde serVIce Time 4 General interaction between a client and a server Connectionless vs connectionoriented protocols reliability vs cost of setting up and tearing down Three Typical Levels of Functionality in the Client Server model User Level Processing application Level Data level Processing Level User interface Usemnterface level HTML page Keyword explesslon comammg list HTML generawr Processing Query Ranked llsl level generator H ofpagetitles RanMng Database queries component t Web pagewes k 7 Wllh metarmformahon Database Va Data level with Web pages L f The general organization of an Internet search engine into three different layers ClientServer Architectures Physically twotiered architecture 7 Many possibilities in distributing functions between C S Physically threetiered architecture 7 Server also acts as a client Multitiered Architectures 1 User interface Client machine Userinterface Userinterface Application I Application Database 7 User interfaoel Userinterface 39 Application 397 quot User interface V 7quot 39 Application i Application J lIApplication Database i Database i i Database i Database i 1 Database Sewer machine a b C d 9 Alternative clientserver organizations a 7 e Multitiered Architectures 2 Wait for result User interface presentation RequeSt Return operation result Wait for data Application server Request data Return data Time Database server An example of a server acting as a client Modern Architectures vertical vs horizontal distribution Front end Re mated Web Servers each requests Contaman the same Web pages An example of horizontal distribution of a Web service More Later Several alternative paradigms to the clientserver model Group multicast Distributed shared memory Distributed objectbased systems Distributed file systems Distributed transactions PeertoPeer Model Publishsubscribe model Remote Procedure Call First suggested by Birrell amp Nelson in 84 Remote ops in the guise of a procedural interface Perform ops on other machines asif they were local No 10 no msg visible to the programmer Middleware Protocols T A llcatlon rotocol T Appllcatron quotquotquot quotPE quotP quot e Mlddleware prolocol Mlddlewave 5 Transport protocol Transport 4 Network protocol Network 3 7 Data llnk protocol H Data link 2 Network Physlcal 1 An adapted reference model for networked communication Conventional Procedure Call Stack polnter Mam program s Main program s local variables v local variables bytes but fd return address read s local varlables a b a Parameter passing in a local procedure call the stack before the call to read b The stack while the called procedure is active Client and Server Stubs Wait for result Client Call remote Return procedure from call Request Reply Server r r r r r r r r r r r r r r r r r r r r r r r r r r r r quot Call local procedure Time A and return results Principle of RFC between a client and server program Steps of a Remote Procedure Call Client procedure calls client stub in normal way Client stub builds message calls local OS Client s OS sends message to remote OS Remote OS gives message to server stub Server stub unpacks parameters calls server Server does work returns result to the stub Server stub packs it in message calls local OS Server s OS sends message to client s OS Client s OS gives message to client stub 0 Stub unpacks result returns to client Issues Why is RPC more than a syntactic change 7 Exchanging messages between different processors arch 7 Littleendian vs bigendian 7 Program execution in different address spaces 7 Character representation 7 Sending pointers What 5 param eter m arshalling uxtrig parameters into a message 7 Exchanging data structures between programs in different languages on two different architectures 7 Should the transport protocol be able to handle this issue Dynamic binding RPC semantics in the presence of failures Passing Value Parameters 1 Client machine Server machine Client process sewer Proceis 1 Client call to Implementat n G Stub makes of add local Call to quotaddquot Server stub jk dd I k as 1 a In 47 Client stub 8 prev add 39addquot 1 mt van 2 Stub builds W L l 539 3353 1m valu message Im39 val g I pron quotadd 39 4 Server OS Cllent 03 l 1 mt valm SewerOS l ands message if 1 nt Va 1 J I to server stub 3 Me age is sent across the network Steps involved in doing remote computation through RPC add in Passing Value Parameters 2 1 3 12 1 1 1 0 01 11 2 1 31 01 1 1 1 1 0 0 0 5 5 0 0 0 0 0 5 31 39 34 4 5 9 1 Al 5 9 1 L L J J L L L L J a b c a Original message on the Pentium little endian b The message after receipt on the SPARC big endian c The message after being inverted The little numbers in boxes indicate the address of each byte Parameter Specification and Stub Generation a A procedure b The corresponding message foobar char x float y int z5 a b Note IDL to support application development Two Extensions to RPC Doors RPC for processes on he same machine Asynchronous RPC Doors Computer Chem woess V Sewerrgmcess sewltrauutl m e uaneluml 7 mm mamll foi lr w im Reg39m d rilddwcrule r A sternum gt I operaung system Inch regrstereu door a amer placess Return to camg mocess The principle of using doors as IPC mechanism Asynchronous RPC l chem Wart tor result Clrent Wan for acceptance r Can remute Return Callremcte Return procedure from call procedure from call Request Request Accept request 5equotquot H Server Can ma pmced Tune 4 Server Call local procedure Time ure and return results E b a The interconnection between client and server in a traditional RPC b The interaction using asynchronous RPC Asynchronous RPC 2 interrupt ciierit Waium acceptance eiiem i Caiiiemom REMquot R t i i from an em 39 Pmcedure J esuiB Acknnwledge R Accept eques request i V Server gt i Time A Can iocai piooediiie oaii chem with e nnemy RP A client and server interacting through two asynchronous RPCs Binding 21 Client to a Server Divemary machine a Look up sewev 1 Chem machine EEL f7 4 Ask for endpmnt 1 Regrsler endpoint Endpuint labia Locate the server s machine Locate the service on that machine RPC Semantics in the Presence of Failures The client is unable to locate the server 0 The request message from the client to the server is lost 0 The server crashes after receiving a request 0 The reply message from the server to the client is lost 0 The client crashes after sending a request Lost Request Messages Server Crashes l REQ Server REQ Server REQ Server Receive Receive Receive Execute Execute REP Reply 2353 25 a b C A server in clientserver communication a Normal case b Crash after execution 0 Crash before execution EECS 49878 Computer Security Peter Honeyman Center for Information Technology Integration Course Overview Course Requirements 0 www citi ulnich edu uhoney security 0 Monday a Friday 9 00 1030 Wednesday 9 00 10 00 1005 Dow 4 credits 0 EECS Technical Elective 0 Presumably working on it o Cryptography and Network Security Principles and Practice Third Edition William Stallings PrenticeHall ISBN 0130914290 0 Weekly or more homework programming assignments 50 o Exams 25 ea Outline of Lectures Outline of Lectures Computer Security 0 Models of security 0 Classical encryption ltgt Substitution and transposition ciphers o Symmetric key cryptography ltgt DES AES others 0 Confidentiality 0 Key distribution 0 Random number generation 0 Number theory Asymmetric key cryptography Message authentication Digital signatures Applications 4 Kerberos SSL X 509 and PKI o IPSec oooo 0 Host security a network security 0 Equallyimportant ltgt Often no clear boundary between them 0 Exam les 0 Morris39 Internet worm ltgt Mitnick39s attack on Shimomura 0 Credit card theft from ecommerce sites 0 Distributed denial of service attacks X800 Security Services X800 Security Services X800 Security Services o Authentication 0 Peer entity identification 4 Guards against masquerade and unauthorized replay 0 Data origin 4 Useful in COVMZCHOHlZSS commun cation 0 Access control 0 Prevent unauthorized use of resources 0 Presupposes some sort of authentication 0 Data confidentiality 0 Fields m amessage 0 Traffic analysis 0 Data integrity 0 Protection from unauthorized modification insertion deletion replay ltgt Granulari 4 Session message or fields 4 Connectionrorienled or connectionless 0 Detection andor recovery X800 Security Services X800 Security Mechanisms Security Attacks o Nonrepudiation 0 Origin sender 0 Destination receiver 0 Availability 0 Security Reliability ltgt Encryption 0 Digital signature Access control 0 0 Data integrity 0 Authentication exchange 0 Traffic padding Routing control o o Notarization 0 Passive attacks 0 Interception 0 Traffic analysis 0 Active attacks 0 Masquerade ltgt Replay 0 Content modification 0 Denial of service Model for Network Security Model for Network Security Designing a Security Service o Principals ltgt Sender ltgt Receiver 0 Adversary 0 Trusted third party ltgt Sender injects message receiver extracts it Sender and receiver communicate over information channel Sender and receiver provide securityrelated information o Poss bly shared Wm or generated b Tap ltgt Securityrelated transformation is applied to message 0 o o Adversary may control information channel 0 Select an algorithm for the securityrelated transformation cipher Generate the securityrelated information to be used by the algorithm keys 0 Select a method for distribution of securityrelated information key distribution 0 Select a protocol for the communicating principals that uses the security algorithm cryptographic protocol Classical Encryption Symmetric Key Cryptography Dimensions of Cryptography o Symmetric or singlekey encryption 0 Model Fig 21 p 25 ltgt Sender combines plairrtext and key to produce ciphertext o Called Ericphermg or encryptan 4 v EKgtlt or v EKgtlt ltgt Receiver combines ciphertext and key to recover ciphertext o Called decipherrigor decryptan 4 gtltDKvorgtlt ltgt Cryptographyis the study of ciphers 0 Type of operations used in cipher ltgt Substitution ltgt Transposition c Number of ke s o Symmetric vs asymmetric o Plaintext processing 0 Block cipher ltgt Stream cipher Cryptosystem Model Goals of Cryptanalysis Cryptanalytic Attacks 0 Fig 2 2 p 26 augments earlier model in two ways 0 Adversary has c mplete information about the encryption and decryption methods 0 o ly m i Q Kerckhoff s pr min N cessary anypraclical cipher 4 Alternatively refer is all rm secret nformalion as rm key 4 Example gzlp l dd cunv swab l irrc o Recover plaintext o Recover key o In all cases cryptanalyst has complete knowledge of the cipher and some ciphertext to be decoded ltgt Ciphertext only 4 Most common attack 0 Known plaintext 4 Cryplanalysl has pla mexlrcipherlexl pars 4 Surprisingly easy to oblan or nfer pla Next 2 4 Cryplanalysl has plainlexlrcipherlexl pa rs Q Cryplanalysl somehow was able is select mg planlexl and force HS encr pilo C ryptanalysis Unconditionally Secure Cipher Computationally Secure Cipher o Chosen ciphertext ltgt Cryptanalyst has plaintextciphertext pairs ltgt Cryptanalyst somehow was able to select the ciphertext and force its decryption o Chosen text 0 Cryptanalyst is able to produce chosen plaintext and chosen ciphertext pairs o A cipher is unconditionally secure if no amount of ciphertext suffices to determine uniquely the plaintext 0 Shannon showed that there is only one cipher that is unconditionally secure 0 It is not practical in most instances o A cipher is computationally secure if 0 The cost of brea ing t e cipher exceeds the value of the encrypted information or o The time required to break the cipher exceeds the useful lifetime of the information 0 Key size plays an important role 0 So does computational power 0 Table 22 p 26 Exhaustive Search and Key Size Computationally Secure Cipher Substitution Ciphers 0 Note that DES can no longer be considered computationally secure 0 Cracking DES Secrets of Encryption Research Wiretap Politics ti Chip Design Electronic Frontier Foundation John Gilmore Editor O39Reilly 6t Associates ISBN 1565925203 ltgt Plaintext characters are replaced by other plaintext characters according to some rule 0 Caesar cipher EC P 3 mod 26 DP c 3 mod 26 o ROT13 EC P 13 mod 26 D E 0 General Caesar cipher EC P k mod 26 ts the key 0 Cryptanalysis try k o 2 o Works tor known or probable plantext Caesar Ciphers Monoalphabetic Substitution Cipher Polygram Substitution Cipher o Cryptanalysis is easy because 0 Algorithm is known 0 Only 26 keys to try 0 Known or probable plaintext o Defeating cryptanalysis ltgt Prescramble plaintext e g compress it 0 Increase the key space o EC P o k mod 26 k o 1oooooogt 7 o Let 2 A B Z 0 Let 1391 2 a E be a permutation 0 Key space is now 26 a 2BE 0 Much too large to search 0 But this is still easy to cryptanalyze through letter frequency analysis 0 ETAOINSHRDLU or something like that ltgt Playfair o EPP QC through keyrbased 5 gtlt 5 transformatton table 4 cryptanalysis dtgram frequency 0 Hill cipher o c KP where c and P are dd menstonal column vectors and K ts a nons ngular dgtlt dmatrtx o P KquotC o Hides d1 letter sequence analysis o Eastty broken wtth known platnlexl hllll r 39 SubstitutionCipl39ler Periodic Substitution Ciphers Periodic Substitution Ciphers o E E a 22 pick one 0 Typically aset of monoalphabetic substitution rules is use 0 Key determines which rule to use 0 Special class of polyalphabetic substitution ciphers 0 Example Vigenere cipher o Each key leller determines one of 26 Caesar ciphers ltgt Ct EU J Pi 39 Kmamimgm o given a sutt cient amount of cipnertext common sequences a e repealed exposing tne period 4 Frequently occurr ng letters n tne key Will be used to encrypt frequently occur plo ntext letters o Vigen re autokey system after key is exhausted use plaintext for running key o Can still detect regularities eg E encrypted with E Vernam Cipher Transposition Rotor Machines o Key length equal to plaintext length o Ak a onetime padquot o Plaintext and ciphertext are statistically independent o Unconditionally secure Shannon 1948 o Key generation and distribution are difficult ltgt Railfence technique 0 Ri ec ehiu nt wttn permuted rows Generalization multiple transpositions 0 Does not change letter frequencies 0 o Enigma ca WWII o Each rotor corresponds to a substitution cipher o A onerotor machine produces a polyalphabetic cipher with period 26 o Output of each rotor is input to next rotor Rotor Machines Chapter 2 Homework Chapter 3 D After each symbol the quotfastquot rotor is rotated D After a full rotation the adjacent rotor is rotate 0 An nrotor machine produces a polyalphabetic cipher with period 260 0 Pick any five problems 0 Extra credit for more than five 0 Simplified DES 0 Block cipher principles 0 DES 0 Block cipher modes of operation Simplified DEs SDES Key Schedule Simplified DEs 0 Block cipher 8bit blocks 0 Input and output 0 10bit key 0 Complex multistage algorithm 0 Five sta es 4 Imiiaipzrmuiaiiona o Keyrdependeni scrambler f 4 Mixes permuiciiiun and supsiiiuiiun 4 Elm key 4 Swap of L and R o f agan different key 4 Inverse permutationIPquot ltgt DES IPquot fKZ swap f IP 0 DES 4 IPquot f swap fa IP 0 10bit key is generator for two 8bit keys K1 and K2 0 K1 select and permuteE paired circular left shiftl permutelOK 0 K2 select and permuteE paired circular left shift2 paired circular left shiftl permutelOK SDES Key Schedule SDES Initial Permutation fK oPermutelO 35274101986 0 Paired circular left shiftl 4 6 0 Select and permuteE 6 3 4 8 5 10 9 o Paired circular left shift2 10 6 7 8 oIP26314857 oIPquot41357286 0 Combination of substitution and permutation Let inputE L4R4 Let F 014 6 014 not necessarily 11 fKL R L F02 K R Note the structure Feistel network 0 We will revisit this soon 0 o o o F F Sboxes o F takes a 4bit input expands it to 8 bits 0 412 3 Z 3 41 0 Then adds the key A1Kn lll Kla nzKm K l 112K15 llS Kls A1KW lll Kla c View this as a matrix 1700 1701 1702 1703 1710 1711 1712 1713 0 First row is fed into Sbox 50 Second row is fed into Sbox 51 0 Each produces two bits 0 Results are concatenated for 4bit output o 5 4x4 matrix of 2bit entries Sboxes SDES Example Analysis of SDES 0 Select row pxyn px3 of 5x 0 Select column p and pxyz of 5x 0 Concatenate and permute the resulting 2bit Sbox entries 4 2 4 3 1 0 Complete the computation of f xor Wilh L append R o N B F is applied only to R but after swapping F is applied to the former L 0 Big hairy example o Exhaustive search brute force on key space 0 Known plaintext attack 0 For each ciphertext bit can write an equation 0 cl 9Pi p2 pg k k2 km 0 8 equations in 10 unknowns many like 29 terms Relationship to DES Block Cipher Principles Block Cipher Principles o DES has 64bit blocks 56bit key 48bit subkeys 16 rounds o F acts on 32bits o 8 5 boxes 4 by 16 containing 4bit values 0 IP 1 fm SW fK15 SW fK1 IP o Stream cipher one bit or byte at a time 0 Eg Vigenere Vernam 0 Block cipher large block typically 8 bytes at a time 0 Large block thwarts statistical attacks o F 2quot a 2quot o F must be reversible ie 11 correspondence 0 2quot bijections On x 2quot bit keys 0 64 bit block u 27 I 102 bit key which is far too long Product Ciphers Product Ciphers Feistel Cipher Structure 0 Apply confusion and diffusion operations to thwart statistical ana ysis ltgt Diffusion 4 mearl leller frequency analysls by dlsslpal mg slallsl cal slruclure mla longrrarlge slallsllcs relal mg plalmlexl and pmerlexl 4 Accompllshed by mak mg each plamlexl cmaracler affect many clpmerlexl cmaraclers 4 Equlvalemly each clpherlexl is affected by many planlexls o Confusion 0 Makes statistical relationship between ciphertext and key complex 0 Generally a complex keydependent substitution algorithm o Substitution on L input 0 Substitution is based on operations applied to R 4 Result lS modlfled L amd arlglmal R allow mg decrypllon ltgt Followed by a permutation swapping L and R 0 Multiple rounds Feistel Cipher Features Feistel Cipher Features Decryption 0 Block size 0 Bigger is better but slower 0 Key size 0 Bigger is better but slower c Number of rounds ltgt SDES 8bit block 10bit key 2 rounds ltgt DES 64bit block 56bit key 16 rounds ltgt Subkey generation algorithm 4 erealer complexlly leads to more Mr cull cryplanalysls 0 Round function 4 erealer complexlly leads to more Mr cull cryplanalysls 0 Hardware vs software speed 4 Fasl sanware mplememlallam lS deslrable 0 Ease of analysis 0 Reverse the encryption steps 0 Recall the Feistel round step L R s R L FK R 0 Reverse with L R R R FK L o F need not be reversible DES DES Round Function Sbox Details 0 64bit block 56bit key 16 rounds 0 48bit subkeys 0 Initial and final inverse permutations o Operates on 32bit units 0 32bit a 48bit expansionpermutation E table 0 XOR with 48 bit subkey o Sbox computation returns 32 bits 0 Round permutation o Followed by Feistel XOR and swap 0 Eight Sboxes each maps 6bits to 4bits 0 One Sbox contains 64 entries each 4bits 0 Can be viewed as four permutations of 0 o The particular permutation is selected with the additional bits added by the E table DES Key Generation DES Decryption DES Avalanche Effect 0 56bit key is split into 28bit L and R o Subkeys are generated by various circular left shifts of L and R o Bits are permuted and selected 0 Just as in SDES apply the subkeys in reverse order 0 The Feistel structure does the rest o In any good cipher any change in the key or plaintext no matter how large or small should change approximately half the ciphertext bits 0 Examples in Table 3 5 on p 81 4 Change one bit in mg plainlexl or key 4 Mar 3 or 4 rounds approximately half of mg cipherlexl bilS are changed 4 Mar 16 rounds a lot of scrambling has mm place 0 Thwarts key guessing attacks Strength of DES DES Design Criteria DES SBox Design Criteria ltgt EFF DES cracker o Brute force attack on 567m key based on Weiner s design 4 250K custom hw exhausts key space n about aweek 4 Final nail in DES coff n o l a m a a v a E o n 1 m l C S 0 Use knowledge of an actual mplememalion under my to m er 2y HS 0 Relies on mmai calculations varying in l me or power depending on input value o Sbox weaknesses o No publicly known weaknesses 0 Design criteria remain classified 0 What we know is based mostly on D Coppersmith The Data Encryption Standard DES and Its Strength Against Attacksquot IBM J ofR and D May 1994 o The Sbox is the only source of nonlinearity in DES o No Sbox output bit should be too close to a linear function of the input bits or any subset of them In practical terms if we select any output bit and any subset of the input bits then the fraction of inputs for which the output bit is the xor of the input bits should be close to 12 0 DES SBox Design Criteria DES SBox Design Criteria Statistical Attacks on DES 0 Each row of an Sbox should be a permutation o If two inputs to an Sbox differ in exactly one bit then the outputs must differ in at least two bits 0 If two inputs to an Sbox differ in exactly the middle two bits then the outputs must differ in at least two bits ltgt Iftwo inputs to an Sbox differ in their first two bits and are identical in their last two bits then the two outputs should not be the s me Etc see text The remaining criteria have mostly to do with avalanche and resistance to differential cryptanalysis o 0 See the text for general information about design criteria for the round function Sbox design and key schedule algorithm design 0 Differential cryptanalysis on Feistel structure 0 Murphy FEAL then Biiham and Shamir DES 0 Look for inputs with some fixed difference that produce outputs with a predictable difference 0 This allows inference of key bits 0 Round by round analysis so more rounds gt more difficult analysis 0 Leads to a 247 chosen plaintext attack Statistical Attacks on DES Statistical Attacks on DES Block Cipher Modes of Operation 0 Linear cryptanalysis ltgt Matsui 0 Also iterated over rounds with decreasing effectiveness 0 247 known plaintexts o Smonewhat surprisingly DES resists differential cryptanalysis o Apparently known to NSA in 70s 0 Eight round LUCIFER requires 28 chosen plaintexts 0 Eight round DES requires 2 chosen plaintexts o How to encrypt more than one block 0 Block modes 0 Electronic codebook ECB ltgt Cipher block chaining CBC o Stream modes 0 Cipher feedback CFB 0 Output feedback OFB 0 Counter mode CTR Electronic Codebook ECB Cipher Block Chaining Initialization Vector Considerations 0 Each plaintext block is independently encrypted with the same key 0 Last block is padded appropriately 0 Useful for transmission of a single block or a small number of blocks 0 Called acodebook because for a given key each block of plaintext produces a unique ciphertext ltgt ECB has certain weaknesses 0 Prior to encrypting a plaintext block xor it with the previous ciphertext block 0 c DESK c l P o P DES 1KC P rl o For first block need initialization vectorquot 0 IV must be known to sender and receiver 0 Stallings and others recommend security for the IV 0 This prevents the adversary from modifying selected bits in the plaintext by complementing corresponding bits in the IV 0 In practice it is effective to use a fixed value say Cipher Feedback Mode Cipher Feedback Decryption Output Feed back Mode o Allows use of DES as a stream cipher 0 Start with IV 0 Encrypt o XOR j bits of output with j bit plaintext 0 Result is ciphertext o Shift IV byj bits insert ciphertext 0 Most efficient to use j 64 0 Reverse steps 0 Start with IV 0 Encrypt o XOR j bits of output with j bit ciphertext 0 Result is plaintext o Shift IV byj bits insert ciphertext ltgt Encrypt IV 0 Shift IV byjbits insert j bits of DES output 0 XOR same jbits of output with jbit plaintext 4 Result is cipherlexl 4 s miiar is a Vernam cipher XOR Wiih PRN6 biis 0 Only use j 64 o Decryption reverses these steps 0 Must not reuse IVkey pair CFB and OFB comparison Counter Mode Other Block Ciphers 0 Errors do not propagate in OFB o This makes OFB vulnerable to modification 0 Similar to OFB but encrypts a counter or Gray code or instead 0 c P DESKU 0 Supports random access 0 Provably as secure as other modes 0 Must not reuse counterkey pair 0 Triple DES o Blowfish o Rijndael Triple DES Meet In The Middle Attack Triple DES 0 First consider double DES 0 C EK2EK1P o 112 bit key is safe from brute force attack 0 But 3 K3 st EK2EK1P EK3P o No DES is not closed 0 Not surprising as DES occupies only atiny portion of the space of 64bit substitution ciphers 0 Let X EKP Clearly X DK2C 0 Given a known ltP 0 construct atable of size 2E with all values of K and EKP 0 Sort on EKP 0 Now decrypt C with all values of K2 Check all results against table 0 Any match is a candidate ltK K2gt pair 0 Total effort is 02 not 2 0 Works for any F f2 f d L v 0 Hence nee 0 C EKIDK2EK3P EDE o No cryptographic significance to middle decrypt operation 4 D and E have equivalent security 4 Allows s ngle DES by sett Vig K ltgt Twokey 3DES K ilt3 EDE o Shorter key is easier to work Wim o Textbook descr bes several impractical attacks 0 Threekey 3DES Other Block Ciphers IDEA IDEA Round Function o IDEA o Blowfish 0 R65 not covered 0 CAST128 0 R62 0 Rijndael AES o Xuejia Lai and James Massey ETH o Patented 0 Used in P6P o 128bit key 64bit block 0 Variant Feistel network 0 Eight rounds final transformation 0 Round function mixes four 16bit blocks 0 Each round takes six 16bit subkeys 4 Final transformation uses four l rbit subkeys 4 Total of 52 su k s o Subkeys are derived through circular Shifts Uses three operations 0 o XOR 4 Addition modulo 2 o Multplcationmodulo 2M1 Blowfish Blowfish Initialization Blowfish Encryption 0 Bruce Schneier ca 93 Freely available Used in SSH OpenBSD IPSec 0 64bit block 32 to 448bit keys 0 Fast encryption small memory footprint 0 Slow key schedule computation Four Srboxes each cohlahlhg 256 32rbllvalu2s o 1E 327m subkeys P array 0 o o P and S are initialized with fractional part of o P is XORed with the key reusing key bits if necessary 0 P and S are churned through Blowfish o 521 executions in total 0 Excellent defense against dictionary attack ltgt Slight variant on classic Feistel network o L and R are bolh processed h each round 4 16 rounds 4 Two extraXORs at the 2 Vld 0 Uses addition modulo 232 and XOR 0 Round functi o a on processes four bytes F lb 6 d Su 52 6 53o 39 SM o Followed by Felslel swap 0 This is fast CAST128 CAST128 Round Function CAST128 Round Function 0 Carlisle Adams and Stafford Tavares 0 Used in IPSec 0 64bit block 40 to 128bit keys 0 Classic Feistel network 0 Sixteen rounds 0 Two subkeys per round one 32bit one 5bit 0 Three different round functions 0 Four operations addition and subtraction modulo 232 XOR and variable circular shift 0 5bit subkey determines shift amount 0 Round function uses four Sboxes o Fixed values 0 Indexed by four 8bit blocks 0 Each contains 256 32bit values 0 32bit values are combined in rounddependent ltgt Produces 32bit output Characteristics of Advanced Block Ciphers Characteristics of Advanced Block Ciphers Rij ndael 0 Variable key length 4 Blemish RC5CAST712E RC2 0 Mixed operators 4 Especially ones that are not associative or distributive ltgt Datadependent rotation 4 RC5 ltgt Keydependent rotation T712E ltgt Keydependent Sboxes ltgt Expensive key schedule computation oBbwm 0 Variable round function 4 CAST712E 0 Variable block length 0 Variable number of rounds 0 Operation on L and R in the round function 0 Selected as AES o 128bit block 128 192 or 256bit key 9 11 or 13 rounds 0 Simple and fast Rijndael Round Function 6F28 6F28 Multiplication o Substitution o Permutation o Multiplication over GFZE 0 Addition over GFZE 0 Not a Feistel network o All representations of a finite field over a prime power in this case 2 are isomorphic 0 Treat a byte b7b6b5b4b3b2blbO as a polynomial ltgt b7x7 b xe b5x5 hm b3x3 bzxz b bnx 0 Addition bitwise modulo 2 ie XOR 1101 0100 0XD4 o Multiplication ltgt Multiplication of polynomials modulo an irreducible binary polynomial of degree 8 o For Rijndael it is 0x113 oxEx4x3x1 6F28 3939rquot 39 Example 6F2 8 6F2 8 0 0x57 gtlt 0x83 0x61 0 010 011 1000 0011 0101 0111 1110 01 0101 1100 0000 010 1011 0111 1001 0X2B79 o 0X2B79 modulo 0X11B 0XC1 gtlt 0 Addition is an Abelian group closed associative ommutative every element has an inverse itself and there is an additive identity O o Multiplication closed associative commutative there is a multiplicative identity 0x01 every element except 0 has an inverse 4 Also anAbelian group ignoring o o Distributive law holds over addition and multiplication ltgt agtltbcabac o GFZE is a field Polynomials with coefficients in C rF28 Rijndael Round Function Rijndael Round Function 0 Treat a fourbyte vector as four coefficients of a polynomial of degree less than four 0 Addition is still XOR o For multiplication use polynomial x4 1 0 Not irreducible but relatively prime to the polynomials we multiply with so the step is invertible o Substitution ltgt Sbox replaces each byte with its multiplicative inverse followed by addition of 0x63 0 Permutation ltgt Represent 16 bytes as 4 x 4 block o i row is shifted by i elements 0 s i s 3 0 Same for 24 bytes 4 x 6 o For 32 bytes 4 x 8 extra shift for rows 2 and 3 o Multiplication of polynomials over GFZE 0 Can be represented as matrix multiplication 0 Addition over GFZE 0 Add round key 0 Initialize with round key addition 0 Last round omits multiply Distributed Naming EECS 498 Farnam J ahanian University of Michigan Reading List Tanenbaum Chapter 4142 43optiona1 DistributedName System Chapter 25 from Computer Networking A Top Down Approach Featuring the Internet 2nd edition Jim Kurose Keith Ross AddisonWesley July 2002 Any problem in computer science can be solved with another layer of indirection Distributed Naming Name string of bits or characters referring to an entity resources services mailboxes newsgroups web pages network connections processors Identifier is the unique name associated with an entity 7 Domain names and URLs are good identi ers 7 39 bameyeecsumichedu identi es ahost identi es a service An entity has an access point and the name associated with an access point is an address 7 eg IP address Location independence a name for an entity ie identifier is independent from its addresses ie name of access points Naming What problem does it solve Naming is a layer of indirection Makes objects hum an readable Hides complexity and dynamics Multiple lowerlayer objects can have one name Changes in lowerlayer objects hidden Allows an object to be found in different ways One object can have multiple names Name Spaces 1 Data stored in n1 n2 quotelkequot n3 quotmaxquot N k n4 steer m 6quot Si quothomeSleenkeysquot lk quot t e 5 max 5 een V V w Leaf node l Directory node B A general naming graph with a single root node 5 mbox Momesteenlmboxquot es are organized into a name space 7 typically represented as a labeled directed graph with leaf nodes and directory nodes Relative Vs absolute path names Linking and Mounting 1 Data stored in n1 n2 eke home n3 maxquot quot L7 quot4 steen39 n1 g Lnd l Ikeys elks maxi steam m n2 n3 Leafnode j d wf Data stored m n6 7 mm mbox keys quotkeysfj Dlreclory node i W C yhomelsteenkeysquot The concept of a symbolic link explained in a naming graph Linking and Mounting 2 Name server Machine A H os I 4 Reference to foreign name space 39T V nfsJflugsvu nllhomesteenquot J Name server for Vorelgn name space Machlne B i Network Mounting remote name spaces through a speci c process protocol Linking and Mounting 3 3homesteenkeysquot N81 NE 3 3 3 l home keys 3 mbox l 1 3 1 3 O to Q Q l elke max steen l l 3 O 5 quot l mbox 1 twmrc V keys Organization of the DEC Global Name Service Name Space Distribution 1 Globai iaer Pm i an 39yaie i J Admim Bug 7 siiaimei U L U e lm i i i Mquot i geiiai iayeri An aiamplepamhomng accessible mes Into thre a The name space 15 aimed inio nonroverlappmg parts called zones 7 each zone 15 impiemenied by a sepamie name server oftheDNS name space includinglnta netr e1 yers Name Space Distribution 2 Omanizatiun FEM Maw Miiiiseennns Secunds Lan immediate Maw Nune eiiew A comparison Depanmem immediate immediate Nune semeiimes Name Resolution Name spaces offer a mechanism for storing and retrieving info about entities by means of names The process oflooking up a name is called name resolution Name resolution service maps names to addresses Iterative vs recursive name names resolution Implementation of Name Resolution 1 1 ltnvucsftpgt Root 777777777777 4 3 2 ltnlgt ltvucsf tpgt 7 3 I n 3 ltVu 81 pgtw 4 4 ltvugt ltcsftpgt I Ode 6 ltcsgt ltftpgt V Ode MW gt Name server 8 ltftpgt cs node Nodes are managed by the same server 5 ltcsf39tpgt ltnvucsf tpgt T Lltnvucsf tpgt Iterative Name Resolution Implementation of Name Resolution 2 1 ltnvucsf tpgt 4 Root 8 ltnIVUCS Pgt name server 7 ltvucs pgtL Name server nlnode 6 ltcsf tpgtk Name server vu node 5 ltf39tpgtL Name server cs node ltnvucsf tpgt T Lltnvucsf tpgt 2 ltvucsf39tpgt 3 ltcsf39tpgt 4 ltf39tpgt Recursive Name Resolution Implementation of Name Resolution 3 Server for Receives and Returns to node Should resolve Looks up Passes to chlld caches requester cs lt pgt lt pgt lt pgt vu ltcs pgt ltcsgt lt pgt lt pgt ltcsgt ltcs a ni ltvucs pgt ltvugt ltcs pgt ltcsgt ltvugt ltcs pgt ltvucsgt ltvucs pgt root ltnivucs pgt ltnlgt ltvucs pgt ltvugt ltngt ltvucsgt ltnvugt ltvucs pgt ltnlvucsgt ltnlvucs pgt Recursive name resolution of ltnl vu cs ftpgt Name servers cache intermediate results for subsequent lookups Implementation of Name Resolution 4 7 i 7quotgt Namesewer nlnode 7quot 1R2 12 Namesewer Chem B r V r V r vunode b 39 39 7 r a 7 Namesewer lm lteratwe name resolution 75 nude Longrdlsmnce communication 5 TL respect to communication costs Domain Name System DNS Distributed directory service DNS is simple but powerful Hierarchical name space Each level separated by 7 Analogous to separator in le systems One global root Replicated across lt20 root servers There have been Denial ofService DoS attacks on these root servers none real success ul Because of caching queries to root servers relatively rare Domain Name System DNS DNS is a Hierarchical name space 7 A subtree is called a domain 7 A path name to its root is called a domain name 7 A domain name can be relative or absolute The name space is divided into nonoverlapping parts called zones mach zone is implemented by a separate name server The contents of a node is defined by a collection of resource records Only one type of query Qu eryd0main name RR type 7 Resource Record RR type is like an attribute type Answervalues additional RRs Limited number of RR types Hard to make new RR typesbut not for technical reasons because each requires global agreement The DNS Name Space I35 235 9quot Description SOA Zone Hoids information on tne represented zone A Host Contains an R address of tne nost tms node represents MX Domain Refers to a maii seiyerto nandie maii addressed to tms node SRV Domain Refers to a server nandiing a specific seryice NS Zone Refers to a name seiyertnat impiements tne represented zone CNAME Node Symbolic link Witn tne primary name oftne represented node PTR Host Contains tne canonicai name ofa nost HlNFO Host Hoids information on tne nost tms node represents TXT Any kind Contains any entity pecific information considered dsefui The most important types of resource records forming the contents of nodes in the DNS name space DNS Implementation 1 Name 9 am type 77 mm value mm s A svzmssstztsua72m350024v92m354m1 An excerpt from imam 5mm m me DNS mm tsucsvunl Emmi scam database for the V m r Vme umwsueu Mam a camp 5 zone mum quot mphyww quot g mmadm w m 1 aswsw m H m Sunumx implemented as xswcsku m KW vu at single zone A no 37275 A HMO MX x A W cums w m NAME HWFO MX m A mm A 170 77 vtmdascswm am U2537t3mnvacdrama wascascswn 3037250 7 7 7 i 7 DNS Implementation 2 Name Record type Record value svu m NS sum as W m sum svu m A 13D 37 21 1 Part of the description for the vunl domain which contains the csvunl domain Primary and Secondary Servers Each zone is implemented by a name server replicated for availability Updates are handled by primary server by modifying local DNS DB Secondary requests the primary server to transfer its content R for all the nodes in a zone are kept in the local DNS DB DNS Cache Management All RRs have Timetolive TTL values When TTL expires cache entries are removed NS RRs tend to have long TTLs reduces load on higherlevel servers A RRs may have very short TTLs l min for web services 1 day for typical hosts 7 What if you want a quick failover for web servers Keep TTL for web server s A RRs very short Why is DNS iterative and not recursive Locating Mobile Entities Section42 Mobile entity 7 An entity whose address often changes laptop running DHCP 7 Not necessarily physical mobility eg dialup Is mobility an issue for DNS 7 NOT REALLY 7 Mobility in practice affects leaf DNS servers A RR TTL is short but NS RR TTL is long What is the problem 7 Most mobile nodes are clients servers are rarely mobile 7 Clients initiate connects not receive it 7 Special cases email instant msg ing VolP Applicationspeci c registration Clients connects to email server IM server SIP server Naming versus Locating Entities 531 Location service Address Address Address Address Address Address 3 b a Direct single level mapping between names and addresses b Two level mapping using identities Separation of naming name 9 identi er from locating identi er 9 current location Location Service Simple solutions for LANs NOT Scalable 7 Broadcasting amp multicasting similar to ARP Drawback in practical for large networks hardware support needed 7 Forwarding pointers when moving from A to B leave a forward reference behind Many drawbacks long chains reliance on intermediate nodes broken links Mobile IP approach homebased approach 7 Introduce a home location that keeps track of current location of an entity 7 Mobile nodes has a stable home address at its home network home agent with xed IP address 7 When a mobile node moves it gets a care of address This address is registered at the home agen 7 When the home agent receives a packet for the mobile node If it s still at home local network just forward the packet Otherwise the packet is tunneled to the current location of the mobile node 9 wrapped in an IP packet and sent to the careofaddress Sender may be informed of the mobile node s current location optional Location Service 0 Issues with Mobile IP approach 7 Increased communication latency a problem in largescale networks Twotier or hierarchical 7 Fixed home location must be highly available 7 What if the nodes moves permanently Use traditional name service Twotier or hierarchical approaches 7 Scalability 7 PCS Forwarding Pointers 1 Process P2 Proxy p refers to s e skeleton as proxy p Process P3 Identical proxy Process P l Skeleton Proxy p Process P4 Object A Local invocation Interprocess 39 communication ldentical skeleton The principle of forwarding pointers using prwcy Skeleton pairs Forwarding Pointers 2 Invncatmn request t5 sent ta object iquot Skeleton at abject s Client proxy sets current process returns 2 shomut the currenl rocatron a rb Redirecting a forwarding pointer by storing a shortcut in a proxy HomeBased Approaches Mobile IP t r 1 Hosts home rocatrun I 2 Return address or current lucatron a Tunnst packeno went rocatron 1 Send successrve packets to current rnmucn The principle ofMobile IP Hierarchical Approaches l Toplevel n domain T The root directory ode d39rT a Directory node dirS of domain 3 A subdomain S 139 of toplevel domain T S is contained In T A leaf domaln contained in S Hierarchical organization of a location service into domains each having an associated directory node Hierarchical Approaches 2 Field with no data W Location record Afor E at node M 7 M Field for domain domN with pointer to N Location record with only one field containing an addres 00 K D 39 D1 omam Domain D2 An example of storing information of an entity having two addresses in different leaf domains Hierarchical Approaches 3 Node knows about E so request Node has no is forwarded to child record for E so that request is forwarded to parent 3 Domain D Looking up a location in a hierarchically organized location service Hierarchical Approaches 4 Nod ows Node has no about E sc request record or E is no longer forwarded Node creates record Vii K and stores pointer T M Node creates V 1 Domain D 1 Insen request a b a An insert request is forwarded to the first node that knows about entity E b A chain of forwarding pointers to the leaf node is created Pointer Caches 1 Domain D Cached Winters E moves regularly between to Ode drD the two subdomains Caching a reference to a directory node of the lowestlevel domain in which an entity will reside most ofthe time Pointer Caches 2 Cached pointer to node dirD which should be invalidated e A but D1 3 kid3323333685 New address A cache entry that needs to be invalidated because it returns a nonlocal address While such an address is available Distributed Snapshot EECS 498 Lecture Notes Prof Farnam Jahanian Univ of Michigan Section 53 Tanenbaum informal description Section 413 Mullender formal description recommended reading Remember Consistent Cuts Consistent cut inconsistent cul Sender of N2 cannot be ident ied with this cut a b a A consistent cut b An inconsistent cut Distributed Snapshot Goal construct a consistent global state in a distributed fashion Without freezing the participating processes Original DS algorithm proposed by Chandy amp Lamport 1985 Assume FIFO delivery through strongly connected uni directional point topoint communication channels between processes System State 7 Local state ofa process application dependent 7 Channel state between apaiI ofprocesses msgs sent but not received Incoming Outgoing message Process State message Local Marker filesystem a a Organization of a process and channels for a distributed snapshot
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'